对于树进行轻重链剖分，对于节点 $x$ ，递归所有轻儿子后消除其影响，递归重儿子，不消除其影响。
然后对于所有轻儿子的子树暴力，从而得到 $x$ 的答案。
对于要消除暴力消除即可。
可以发现如果暴力到点 $u$ 必然是其 $u$ 到根的轻边数量，从而时间复杂度除在统计每个节点答案时其余时间复杂度为 $O(n\log n)$ 。
模板题，按上述过程模拟即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define int long long using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-‘0‘;c=getchar();} return ans*f; } const int MAXN=100001; struct node{ int u,v,nex; }x[MAXN<<1]; int head[MAXN],cnt,N,A[MAXN]; void add(int u,int v){ x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++; } int Cnt[MAXN],Mx,sum,Ans[MAXN],V,siz[MAXN],son[MAXN]; void dfs(int u,int fath){ siz[u]=1; for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; dfs(x[i].v,u);siz[u]+=siz[x[i].v]; if(siz[son[u]]<siz[x[i].v]) son[u]=x[i].v; }return; } void dfs1(int u,int fath,int w){ Cnt[A[u]]+=w; if(Cnt[A[u]]>Mx) Mx=Cnt[A[u]],sum=A[u]; else if(Cnt[A[u]]==Mx) sum+=A[u]; for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath||x[i].v==V) continue; dfs1(x[i].v,u,w); }return; } void dfs(int u,int fath,int opt){ for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath||x[i].v==son[u]) continue; dfs(x[i].v,u,0); } if(son[u]) dfs(son[u],u,1); V=son[u];dfs1(u,fath,1); Ans[u]=sum; if(!opt) V=0,dfs1(u,fath,-1),Mx=sum=0; } signed main(){ memset(head,-1,sizeof(head)); N=read(); for(int i=1;i<=N;i++) A[i]=read(); for(int i=1;i<N;i++){ int u=read(),v=read(); add(u,v),add(v,u); } dfs(1,0);dfs(1,0,0); for(int i=1;i<=N;i++) printf("%lld ",Ans[i]);printf("\n"); return 0; }
或者可以线段树合并，利用线段树维护颜色个数。
可以长链剖分也可以 $dsu$ ，$dsu$ 的时间复杂度 $O(n\log n)$ 。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-‘0‘;c=getchar();} return f*ans; } const int MAXN=1000001; struct node{ int u,v,nex; }x[MAXN<<1]; int dep[MAXN],cnt,siz[MAXN],son[MAXN],N,head[MAXN]; int Ans[MAXN]; void add(int u,int v){ x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++; } void dfs0(int u,int fath){ siz[u]=1;dep[u]=dep[fath]+1; for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; dfs0(x[i].v,u);siz[u]+=siz[x[i].v]; if(siz[son[u]]<siz[x[i].v]) son[u]=x[i].v; }return; } int Num[MAXN],Mx,Sum,Lim; void Add(int u,int fath,int w){ Num[dep[u]]+=w; if(Num[dep[u]]>Mx) Mx=Num[dep[u]],Sum=dep[u]; else if(Num[dep[u]]==Mx&&dep[u]<Sum) Sum=dep[u]; for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath||x[i].v==Lim) continue; Add(x[i].v,u,w); }return; } void dfs1(int u,int fath,int opt){ // cerr<<u<<" "<<fath<<" "<<opt<<endl; for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath||x[i].v==son[u]) continue; dfs1(x[i].v,u,0); } if(son[u]) dfs1(son[u],u,1);Lim=son[u]; Add(u,fath,1);Ans[u]=Sum; Lim=0; if(!opt) Add(u,fath,-1),Mx=Sum=0; return; } int main(){ // freopen("maker.in","r",stdin); memset(head,-1,sizeof(head)); N=read(); for(int i=1;i<N;i++){int u=read(),v=read();add(u,v),add(v,u);} dfs0(1,0);dfs1(1,0,0); for(int i=1;i<=N;i++){ printf("%d\n",Ans[i]-dep[i]); } return 0; }/* 8 1 2 2 3 1 4 3 5 4 6 5 7 4 8 */
对于重儿子为 $u$ 下面最深的链所在儿子，可以发现最多到根有 $\sqrt{n}$ 个长链与短链，因为对于每次走到轻边必加上比他深的儿子,可以写成 $1+2+…x=n->x=\sqrt{n}$ 。
如果一个子树 $dp$ 只与深度有关，则可能可以使用长链剖分的方法优化它的复杂度。
详细情况请参考 $link$ 。考虑对于继承每个重儿子的话可以用指针维护吗，或者数组 $hash$ 即可。
虽然可以 $dsu$ ，但是通过长链剖分可以得到更优的复杂度 $O(n)$ 。时间复杂度为 $O(n)$ 因为每条重链只统计一次。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-‘0‘;c=getchar();} return f*ans; } const int MAXN=1000001; struct node{ int u,v,nex; }x[MAXN<<1]; int N,head[MAXN],cnt,tmp[MAXN],*id=tmp,*f[MAXN],len[MAXN],son[MAXN],Ans[MAXN]; void add(int u,int v){ x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++; } void dfs(int u,int fath){ for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; dfs(x[i].v,u);if(len[son[u]]<len[x[i].v]) son[u]=x[i].v; }len[u]=len[son[u]]+1;return; } void dfs1(int u,int fath){ f[u][0]=1;if(son[u]) f[son[u]]=f[u]+1,dfs1(son[u],u),Ans[u]=Ans[son[u]]+1; for(int i=head[u];i!=-1;i=x[i].nex){ if(x[i].v==fath||x[i].v==son[u]) continue; f[x[i].v]=id,id+=len[x[i].v];dfs1(x[i].v,u); for(int j=1;j<=len[x[i].v];j++){ f[u][j]+=f[x[i].v][j-1]; if((f[u][j]>f[u][Ans[u]])||(f[u][j]>=f[u][Ans[u]]&&j<Ans[u])) Ans[u]=j; } } if(f[u][Ans[u]]==1) Ans[u]=0;return; } int main(){ // freopen("4.in","r",stdin); memset(head,-1,sizeof(head));N=read(); for(int i=1;i<N;i++){int u=read(),v=read();add(u,v),add(v,u);} dfs(1,0);f[1]=id,id+=len[1];dfs1(1,0); for(int i=1;i<=N;i++) printf("%d\n",Ans[i]); return 0; }/* 4 1 2 2 3 3 4 */
原文：https://www.cnblogs.com/si-rui-yang/p/12045828.html
