对树长链剖分，dp令f[i][j]表示第i个点为根的子树中第j种颜色的数量，直接暴力dfs，对于每个节点，先dfs重儿子并直接继承重儿子的信息，再搜索轻儿子并合并，这样的时间复杂度是$o(nlog_{2}n)$的（当然好像直接不按顺序暴力合并也可以过，数据比较水）。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<map> 5 using namespace std; 6 #define fo(i,a,b) for(int i=a;i<=b;i++) 7 #define ll long long 8 #define maxN 100001 9 #define maxM 100001 10 map<int,int>cnt[maxN]; 11 struct ji{ 12 int nex,to; 13 }edge[maxN<<1]; 14 int E,n,x,y,head[maxN],f[maxN],id[maxN],c[maxN]; 15 ll tot[maxN],a[maxN]; 16 void add(int x,int y){ 17 edge[E].nex=head[x]; 18 edge[E].to=y; 19 head[x]=E++; 20 } 21 void merge(int x,int y){ 22 if (cnt[id[x]].size()<cnt[id[y]].size())swap(id[x],id[y]); 23 for(map<int,int>::iterator p=cnt[id[y]].begin();p!=cnt[id[y]].end();p++) 24 if ((cnt[id[x]][p->first]+=p->second)>=f[id[x]]){ 25 if (cnt[id[x]][p->first]>f[id[x]])tot[id[x]]=0; 26 tot[id[x]]+=p->first; 27 f[id[x]]=cnt[id[x]][p->first]; 28 } 29 } 30 void dfs(int k,int fa){ 31 f[k]=cnt[id[k]=k][tot[k]=c[k]]=1; 32 for(int i=head[k];i!=-1;i=edge[i].nex) 33 if (edge[i].to!=fa){ 34 dfs(edge[i].to,k); 35 merge(k,edge[i].to); 36 } 37 a[k]=tot[id[k]]; 38 } 39 int main(){ 40 memset(head,-1,sizeof(head)); 41 scanf("%d",&n); 42 for(int i=1;i<=n;i++)scanf("%d",&c[i]); 43 fo(i,1,n-1){ 44 scanf("%d%d",&x,&y); 45 add(x,y); 46 add(y,x); 47 } 48 dfs(1,0); 49 fo(i,1,n)printf("%lld ",a[i]); 50 }