前言：树上启发式合并(DSU on Tree)，是一个在O(nlogn) 时间内解决许多树上问题的有力算法，其对于树上离线问题的处理速度大于等于其他的算法，且更容易理解(个人认为处理与子树的关系牵涉很多)。具体思路大概就是先像树链剖分那样找到每个结点的重儿子，然后把所有轻儿子的贡献合并于重儿子(比较抽象吧~),当前结点操作完毕之后，再看如果当前结点是其父亲结点的一个轻儿子，那么该轻儿子贡献全部置0。对于重儿子的贡献保留。至于时间复杂度为什么是O(logn)，我也不太会证明，但是肯定比在线暴力对每个儿子操作其全部结点快，因为首先Dsu On Tree是个离线算法，你每次对当前结点的操作，实际是只要处理轻儿子结点(重儿子结点贡献已经有了)，这么来看你就较常规方法少了再遍历重儿子的那一步，时间复杂度自然而然就降了。
←大概就是这个样子吧OvO
我觉得理解一个算法的，重要的一步是训练刷题+总结，所以我附上一些刷题题单，前面几个题会简单一些(CF2300分左右)，最后一个题有点难(CF2900分)
接下来我一道题一道题地写一下解析叭：
A：Codeforces-600E(Lomsat Gelral)
题意：对于每个子树，输出子树中出现次数最多的节点编号之和。（次数最多的编号有多个节点都要统计进去）
解法：这是一道比较模板的树上启发式合并题，每一次count，统计当前颜色col[u]出现的次数即cnt[col[u]]。如果其次数大于所有颜色中出现次数最多颜色的大小maxc,即把maxc更新成当前结点的颜色大小cnt[col[u]],同时更新sum。另外该题要求如果子树中出现颜色次数一样，那么和就等于这些相同颜色值大小和，所以你还需要特判更新一波。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ‘\n‘ #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int col[maxn],cnt[maxn]; int siz[maxn],son[maxn]; void dfs(int u,int f){ siz[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==f) continue; dfs(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]){ son[u]=v; } } } ll ans[maxn],sum; int flag,maxc; void count(int u,int f,int val){ cnt[col[u]]+=val; if(cnt[col[u]]>maxc){ maxc=cnt[col[u]]; sum=col[u]; } else if(cnt[col[u]]==maxc) sum+=col[u]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==f||v==flag) continue; count(v,u,val); } } void dfs(int u,int f,bool keep){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==f||v==son[u]) continue; dfs(v,u,false); } if(son[u]){ dfs(son[u],u,true); flag=son[u]; } count(u,f,1); flag=0; ans[u]=sum; if(!keep){ count(u,f,-1); sum=maxc=0; } } int main(){ int n;scanf("%d",&n); mem(head,-1); rep(i,1,n) scanf("%d",&col[i]); rep(i,1,n-1){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0); dfs(1,0,0); rep(i,1,n) printf("%lld ",ans[i]); puts(""); }
B：Codeforces-246E(Blood Cousins Return)
题意：给定一棵树，已知每个节点的父亲节点，和每个节点上的名字(字符串)，对于每个询问vi,ki，求子树vi内v的kth层儿子(子树内比子树根深度大k层的部分)中不重复名字的个数。
解法：因为有可能是森林，所以你需要统计一共有多少个树rootcnt,并记录每个数的根节点root[i](判断其是否为某个数根节点只需要看它父亲是不是0就行啦)，利用map离散化一下，就把名字当成颜色好了。同时count的时候也要注意某子树如果当前结点为u当前层中该颜色即col[u]是否在其他子树出现过，即也用map来记录一下，如果没有那ok，如果有的话，当前层次的颜色你就不需要再更新啦！另外值得一提的是：对于结点询问，如果只给你某个结点的v和第几层d，那么可以用vector<pair<int,int>> q[maxn]来记录，第一个q[u]记录结点v，q[u][i].first记录询问的id，q[u][i].second记录层次。然后你统计当前询问的时候，只需要看当前结点u是否充当v的时候q[u].size()是否>0，若如此则说明有询问坐落于该结点上。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ‘\n‘ #define eps 0.000000001 #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int n;map<string,int> mp;int c[maxn],root[maxn]; vector<pair<int,int> >q[maxn]; int siz[maxn],son[maxn],dep[maxn]; void dfs1(int u,int f){ dep[u]=dep[f]+1; siz[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } int flag,ans[maxn]; int cnt[maxn]; map<pair<int,int>,int> pk; void count(int u,int f,int val){ if(val==1&&!pk[{dep[u],c[u]}]) cnt[dep[u]]+=val,pk[{dep[u],c[u]}]+=val; if(val==-1&&pk[{dep[u],c[u]}]) cnt[dep[u]]+=val,pk[{dep[u],c[u]}]+=val; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==f||v==flag) continue; count(v,u,val); } } void dfs(int u,int f,int keep){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==f||v==son[u]) continue; dfs(v,u,0); } if(son[u]){ dfs(son[u],u,1); flag=son[u]; } count(u,f,1); for(int i=0;i<q[u].size();i++){ int id=q[u][i].first; int d=q[u][i].second; ans[id]=cnt[dep[u]+d]; } flag=0; if(!keep){ count(u,f,-1); } } int main(){ cin>>n;mem(head,-1); int cntcolor=0;int cntroot=0; rep(i,1,n){ string s;int x;cin>>s>>x; if(!mp[s]) mp[s]=++cntcolor; c[i]=mp[s]; if(!x){ ++cntroot; root[cntroot]=i; }else{ add(x,i);add(i,x); } } int m;cin>>m; rep(i,1,m){ int u,d;cin>>u>>d; q[u].push_back({i,d}); } rep(i,1,cntroot){ dfs1(root[i],0); } rep(i,1,cntroot){ dfs(root[i],0,0); } rep(i,1,m){ cout<<ans[i]<<endl; } }
原文：https://www.cnblogs.com/Anonytt/p/13085122.html
