树上启发式合并 \((dsu\ on \ tree)\)
适用条件：
可以在一个子树内统计的问题，并且不带修改。暴力复杂度一般为 \(O(n^2)\)。
例题：
CF600E Lomsat gelral
解法
考虑一个问题 ，给你一棵树，每个节点有一个颜色，如果一种颜色在以 \(x\) 为根的子树内出现次数最多，则称 \(col_i\) 占主要色。求算对于每一个 \(i∈[1,n]\)，求以 \(i\) 为根的子树中，占主导地位颜色编号和。
我们考虑 dsu on tree。首先维护出每个节点的重儿子 \(son_i\)，而后我们考虑写这样一个 dfs 函数求答案。
首先对于 \(u\) 为根的子树遍历所有的轻儿子，再遍历所有的重儿子，这样就可以求得 \(u\) 子树内所有答案了。这时候我们考虑求算 \(u\) 点的答案，这时候我们求算过的所有的轻儿子答案已经被清空掉了，只剩下子树内重儿子的答案 \(sum\)。这时候我们考虑只暴力遍历轻儿子加入答案即可。
复杂度为 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+7;
int n,col[N];
vector<int> G[N];
int sz[N],dep[N],son[N];
int num[N],sum,maxN;
int ans[N];
void dfs(int u,int father){
sz[u]=1;
for(int k:G[u]){
if(k==father) continue;
dfs(k,u);sz[u]+=sz[k];
if(!son[u]||sz[k]>sz[son[u]]) son[u]=k;
}
}
void updata(int u,int father,int son,int val){
num[col[u]]+=val;
if(num[col[u]]>maxN) maxN=num[col[u]],sum=col[u];
else if(num[col[u]]==maxN) sum+=col[u];
for(int k:G[u]){
if(k!=father&&k!=son) updata(k,u,son,val);
}
}
void DFS(int u,int father,bool kep){
for(int k:G[u]){
if(k!=father&&k!=son[u]) DFS(k,u,0);
}
if(son[u]) DFS(son[u],u,1);
updata(u,father,son[u],1);
ans[u]=sum;
if(!kep) updata(u,father,-1,-1),sum=maxN=0;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&col[i]);
for(int i=1;i<n;i++){
int u,v;scanf("%lld%lld",&u,&v);G[u].push_back(v),G[v].push_back(u);
}
dfs(1,-1);DFS(1,-1,1);
for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
return 0;
}
CF208E Blood Cousins
解法
对于一棵树，或者一座森林，询问 \((v,p)\) 表示编号为 \(v\) 的人有多少个 \(p\) 级表亲。
我们考虑 dsu on tree。首先我们从 \(v\) 跳到 \(p\) 级祖先 \(u\)，然后我们考虑在 \(u\) 所在子树内统计深度为 \(dep[u]+p\) 的点数量和。dsu on tree 思路同上一题。
注意：
- 我们建一个虚拟根 \(0\) 号点便于我们进行 dfs，但是我们在判断是否有解的情况时不能把 \(0\) 当作 \(v\) 的 \(p\) 级祖先，因而我们判断时需要满足
dep[x]>p+1才有解，反之无解。 - 注意计算贡献或删除贡献时不要重复计算或删除。
- 因为对于每个子树，\(v\) 也被计算过一次，因而最后答案要减一。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n;
vector<int> G[N];
vector<pair<int,int> > Q[N];
int sz[N],dep[N],son[N];
int cnt[N];
int ans[N];
int f[100000][30];
int q;
void dfs(int u,int father){
f[u][0]=father,dep[u]=dep[father]+1;
sz[u]=1;
for(int k:G[u]){
if(k==father) continue;
dfs(k,u);sz[u]+=sz[k];
if(!son[u]||sz[k]>sz[son[u]]) son[u]=k;
}
}
void updata(int u,int father,int son,int val){
cnt[dep[u]]+=val;
for(int k:G[u]){
if(k!=father&&k!=son) updata(k,u,son,val);
}
}
void DFS(int u,int father,bool kep){
for(int k:G[u]){
if(k!=father&&k!=son[u]) DFS(k,u,0);
}
if(son[u]) DFS(son[u],u,1);
updata(u,father,son[u],1);
for(auto it:Q[u]){
int _dep=it.first,_id=it.second;
ans[_id]=cnt[_dep];
}
if(!kep) updata(u,father,-1,-1);
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int fa;scanf("%d",&fa);
G[fa].push_back(i);
}
dfs(0,-1);
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
int x,d;
scanf("%d%d",&x,&d);
if(dep[x]<=d+1) continue;
for(int k=0;k<=20;k++){
if((1<<k)&d) x=f[x][k];
}
Q[x].push_back(make_pair(dep[x]+d,i));//亲戚的深度和问题编号。
}
DFS(0,-1,-1);
for(int i=1;i<=q;i++) printf("%d ",ans[i]==0?0:ans[i]-1);
return 0;
}