参考：p_z_y 的博客，YellowBean 的代码启示。
尽量写短点。
dsu on tree
模板题：CF600E Lomsat gelral。
题意：
- 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。
- 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。
- 如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
- 你的任务是对于每一个 $i\in[1,n]$，求出以 $i$ 为根的子树中，占主导地位的颜色的编号和。
- $n\le 10^5,c_i\le n$。
首先我们考虑 $n^2$ 的做法，对于每一个点遍历整棵子树暴力统计答案即可。
好了，dsu on tree 完成一半了。
我们发现子树和父亲之间有很多结点是重复的，考虑把他利用上。我们无法同时保存两个儿子所在子树的结果，因为我们在处理另一个儿子的答案时，已有的信息会对其产生干扰。我们可以做的仅仅是对于最后遍历的那个儿子，我们保留其信息，而对于之前遍历的儿子，只能清除。
猜测保留重儿子的信息是最优的，因为这样不同统计的结点最多。这就是 dsu on tree了。
具体的实现（引用自 p_z_y 的博客）：
- 遍历所有轻儿子，递归结束时消除它们的贡献。
- 遍历重儿子，保留它的贡献。
- 再计算当前子树中所有轻子树的贡献。
- 更新答案。
即：先处理完轻儿子的答案并消除贡献，再去处理重儿子的答案并保留贡献，再暴力统计轻儿子的贡献从而得出当前结点的答案即可。
代码部分
建树后，先处理出轻儿子。
inline void dfs1(int u,int f){
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
接着直接 dsu on tree，详见注释。
inline void Dfs(int u,int f,int p){//暴力统计贡献
t[c[u]]++;
if(t[c[u]]>mx){
mx=t[c[u]];
sum=c[u];
}
else if(t[c[u]]==mx) sum+=c[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==f||v==p) continue;
Dfs(v,u,p);//重儿子答案统计好了，不用跑也不能跑
}
}
inline void clean(int u,int f){//消除贡献
t[c[u]]--;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==f) continue;
clean(v,u);
}
}
inline void dfs(int u,int f){//dsu on tree 主函数
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f||v==son[u]) continue;
dfs(v,u);clean(v,u);sum=mx=0;//处理轻儿子并消除贡献
}
if(son[u]) dfs(son[u],u);//处理重儿子，不消除贡献
Dfs(u,f,son[u]);ans[u]=sum;//暴力跑完轻儿子后统计答案
}
复杂度证明
由于每一个点到根最多只有 $\log n$ 条轻边，而我们发现一个点到根每有一条轻边，其就会被暴力统计贡献一次，因此一个点最多被暴力统计 $\log n$ 次，故时间复杂度为 $O(n\log n)$。
几道例题
题意:
- 给定一个以 $1$ 为根的 $n$ 个结点的树，每个点上有一个字母（
a–z），每个点的深度定义为该节点到 $1$ 号结点路径上的点数。每次询问 $a, b$ 查询以 $a$ 为根的子树内深度为 $b$ 的结点上的字母重新排列之后是否能构成回文串。
发现能构成回文串当且仅当奇数个数的字母种数不大于 $1$。记 $t_{dep,0\sim25}$ 为深度为 $dep$ 的点中各个字母出现的次数，用 dsu on tree 处理再每次遍历 $26$ 个字母统计答案即可。
题意：
- 给定一片森林，每次询问一个节点的 K-Son 共有个多少不同的名字。一个节点的 K-Son 即为深度是该节点深度加 $K$ 的节点。
跟上题差不多，用 map 存每层每个名字出现了多少次，再给每一次搞一个 set，新名字丢进去，名字没了删掉，然后统计答案时直接调出其中的 size 即可。
题意：
- 给你一片森林，每次询问一个点与多少个点拥有共同的 $K$ 级祖先。
先倍增跑出询问点的 $K$ 级祖先是谁，再把询问打在这个 $K$ 级祖先上，就变成了统计子树内某个深度的点有多少个，容易用 dsu on tree 解决。
后加的一道题，题意懒得写了。
用树状数组+启发式合并优化一下 dp。
完整代码（CF600E）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,c[N],mx;
ll sum,ans[N];
struct node{
int to,nxt;
}e[N<<1];
int cnt,head[N],t[N];
inline void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int son[N],siz[N];
inline void dfs1(int u,int f){
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
inline void Dfs(int u,int f,int p){
t[c[u]]++;
if(t[c[u]]>mx){
mx=t[c[u]];
sum=c[u];
}
else if(t[c[u]]==mx) sum+=c[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==f||v==p) continue;
Dfs(v,u,p);
}
}
inline void clean(int u,int f){
t[c[u]]--;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==f) continue;
clean(v,u);
}
}
inline void dfs(int u,int f){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f||v==son[u]) continue;
dfs(v,u);clean(v,u);sum=mx=0;
}
if(son[u]) dfs(son[u],u);
Dfs(u,f,son[u]);ans[u]=sum;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,1);
dfs(1,1);
for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
return 0;
}
评论