核心思想

借用了一个节点到根的路径上轻边个数不会超过logn条。

故重节点保留，轻节点删去，多重统计。

实际复杂度（nlogn）

例题

Lomsat gelral - 洛谷

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int col[100010],ans[100010];
vector<int> g[100010];
int son[100010];
int sz[100010];
int sum,mx;
int Son;
int cnt[100010];
void dfs1(int u,int fa){sz[u] = 1;for(int v:g[u]){if(v == fa)continue;dfs1(v,u);sz[u]+=sz[v];if(sz[son[u]]<sz[v]){son[u] = v;}}
}
void add(int u,int fa,int val){cnt[col[u]]+=val;int tp = col[u];if(cnt[tp] > mx){mx = cnt[tp];sum = tp;}else if(cnt[tp] == mx){sum+=tp;}for(int v:g[u]){if(v == fa||v == Son)continue;add(v,u,val);}
}
void dfs2(int u,int fa,int opt){for(int v:g[u]){if(v == fa||v == son[u])continue;dfs2(v,u,0);}if(son[u]){dfs2(son[u],u,1),Son = son[u];}add(u,fa,1);Son = 0;ans[u] = sum;if(!opt){add(u,fa,-1),sum = mx = 0;}
}
signed main(){cin>>n;for(int i = 1;i <= n;i++)cin>>col[i];for(int i = 1;i < n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}dfs1(1,0);dfs2(1,1,0);for(int i = 1;i <= n;i++){cout<<ans[i]<<" ";}return 0;
}