dsu on tree 学习笔记_零衣贰的博客-爱代码爱编程
Dsu On Tree 模板 CF600E Lomsat gelral
-
我们显然要维护以每一个节点为根的子树内的颜色信息
-
对于一个节点 u u u,我们已经知道他的儿子 a , b , c a,b,c a,b,c 子树的信息,如何将子树的信息转移到节点 u u u ?
- 如图:
- 如图:
-
朴素的想法:
将所有子树的信息逐一传递给父亲:那么其时间复杂度为 s i z e ( a ) + s i z e ( b ) + s i z e ( c ) size(a) + size(b) + size(c) size(a)+size(b)+size(c) 为 O ( n ) O(n) O(n) 的复杂度,那么维护整棵树就是 O ( n 2 ) O(n^2) O(n2) 的复杂度
-
优化:
-
我们现在的操作相当于将 a , b , c a,b,c a,b,c 三个结点的信息传递到节点 u u u 上,
节点 u u u 的信息初始为空,为 [ R e d : 0 ] [ B l u e : 0 ] [ G r e e n : 0 ] [Red:0][ Blue:0][Green:0] [Red:0][Blue:0][Green:0],
传递 a a a 后变为 [ R e d : 4 ] [ B l u e : 2 ] [ G r e e n : 0 ] [Red:4][Blue:2][Green:0] [Red:4][Blue:2][Green:0],
传递 b b b 后变为 [ R e d : 6 ] [ B l u e : 2 ] [ G r e e n : 1 ] [Red:6][Blue:2][Green:1] [Red:6][Blue:2][Green:1],
传递 c c c 后变为 [ R e d : 6 ] [ B l u e : 3 ] [ G r e e n : 2 ] [Red:6][Blue:3][Green:2] [Red:6][Blue:3][Green:2] -
我们不妨将 u u u 的初始信息设置为 a a a 的信息,再将 b , c b,c b,c 的信息传递给 u u u ,就等价于将 a , b , c a,b,c a,b,c 信息传到空的 u u u 上
这样 u u u 初始为 [ R e d : 4 ] [ B l u e : 2 ] [ G r e e n : 0 ] [Red:4][Blue:2][Green:0] [Red:4][Blue:2][Green:0]
传递 b b b 后变为 [ R e d : 6 ] [ B l u e : 2 ] [ G r e e n : 1 ] [Red:6][Blue:2][Green:1] [Red:6][Blue:2][Green:1],
传递 c c c 后变为 [ R e d : 6 ] [ B l u e : 3 ] [ G r e e n : 2 ] [Red:6][Blue:3][Green:2] [Red:6][Blue:3][Green:2]
两者效果完全相同,但后者复杂度为 s i z e ( b ) + s i z e ( c ) size(b)+size(c) size(b)+size(c) -
如果我们每次都选择将 u u u 初始设为子树结点最多的儿子(即重儿子),再逐一转移其余儿子 ( 即轻儿子),可证得最终维护整棵树的复杂度为 O ( n l o g n ∗ ( 转 移 复 杂 度 ) ) O(nlogn * (转移复杂度)) O(nlogn∗(转移复杂度))
-
根据以上思路,我们不难得到以下代码
-
// O(nlogn * logn)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,col[MAXN],siz[MAXN],ans[MAXN];
vector <int> G[MAXN];
map <int,int> cnt[MAXN]; //cnt[u][c] : u 子树内颜色为 c 的个数
int mx, mxson, sum;
void dfs(int u,int fa)
{
//siz[u] : u 子树的大小
//mxson : 子树结点个数最大的儿子(重儿子)
siz[u]=1;
mx=0, mxson=0;
for(auto v:G[u])
{
if(v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
if(siz[v]>mx)
{
mx=siz[v];
mxson=v;
}
}
if(mxson != 0)// 初始设为重儿子的信息
{
cnt[u] = cnt[mxson];
}
cnt[u][col[u]] ++ ;
//传递其余儿子(轻儿子)的信息
for(auto v:G[u])
{
if(v==fa) continue;
if(v==mxson) continue;
for(auto x:cnt[v])
{
cnt[u][x.first] += x.second;
}
}
//求出现次数最多颜色编号之和
mx=0, sum=0;
for(auto x:cnt[u])
{
if(cnt[u][x.first] > mx)
{
sum = x.first;
mx = cnt[u][x.first];
}
else if(cnt[u][x.first] == mx)
{
sum += x.first;
}
}
ans[u] = sum;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>col[i];
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
}
-
- 这样仍然需要优化
- 这时候我们的
cnt
数组就应该只开一维 - 这时我们思路的应变:
- 对于遍历的一个结点 u u u
- 遍历轻儿子,算出轻儿子的信息
- 遍历重儿子,不消除影响
- 统计轻儿子贡献,将轻儿子的信息传递给父亲 u u u
- 更新 u u u 的答案
- 删除轻儿子的影响(
cnt
数组只有一个,消除轻儿子对其他节点的影响)
- 这时候我们的