題意
有一顆 n n n 個節點的樹，以 1 1 1 為根節點，每個點有一個顔色 v i v_i vi。設子樹 a a a 中顔色出現次數最多的顔色集合為 { b i } \{b_i\} {bi}，記 a n s a = ∑ b i ans_a=\sum b_i ansa=∑bi。現在要求 a n s 1 , a n s 2 , . . . . a n s n ans_1,ans_2,....ans_n ans1,ans2,....ansn。
其中， n , v ≤ 1 0 5 n,v\leq 10^5 n,v≤105。
分析
這種題叫做 d s u o n t r e e dsu~on~tree dsu on tree，也就是樹上啟發式合并。
讓我們先考慮暴力做法。
就是以每個節點，對子樹進行 d f s dfs dfs，然後開一個桶記錄顔色出現次數，最後把顔色出現次數最多的顔色加起來。這樣子做複雜度是 O ( n 2 ) O(n^2) O(n2) 的。
這複雜度顯然是不可接受的嘛！暴力差就差在，它計算了很多重複的東西！如果我們能讓重複的東西盡量減少計算，複雜度就能夠得到提升了！
看到這道題，有的同學可能一下子想的是樹上莫隊。
确實，莫隊算法就是用來優化這些有重複計算的東西的。
不過，更優秀的算法是用啟發式合并，複雜度可以做到 O ( n l o g n ) O(nlogn) O(nlogn)。
一句話解釋這個算法，就是保留重兒子的結果，暴力疊代輕兒子。
重兒子是什麼？
如果你學過樹鍊剖分，就能一下子知道了。不過沒學過也沒關系。重兒子就是這個節點所有兒子中 s i z siz siz 最大的點。如圖：
x x x 的 s i z siz siz 最大，是以 x x x 是 r t rt rt 的重兒子。
記 t o t i tot_i toti 為顔色 i i i 的出現次數。
我們要讓重複求的東西盡量少，但是子樹之間又互相獨立，于是我們隻能欽點一個子樹來保留 t o t tot tot 的值。既然重兒子如此牛逼，那我們就欽點重兒子吧！
假設我們現在要求 a n s r t ans_{rt} ansrt，我們已經保留了 x x x 子樹的 t o t tot tot 數組。
那我們從 r t rt rt 開始周遊一遍子樹，如果遇到 y , z y,z y,z，就繼續往下 d f s dfs dfs，求出 t o t tot tot。如果遇到 x x x，那麼就可以 r e t u r n return return 了，因為之前求過 t o t tot tot 了。再求一遍不是智障了嗎？？
這樣子，單次求 a n s r t ans_rt ansrt 的複雜度是 s i z r t − s i z x siz_{rt}-siz_{x} sizrt−sizx 的。
寫成代碼的話長這樣：
關于複雜度
不妨考慮每個點會被通路多少次。
如果一個節點到根節點有 x x x 條輕邊，那麼這個節點會被通路 x x x 次。
由于一個節點到根節點的輕邊數量不超過 l o g n logn logn 條。
于是總的複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)
後記
為什麼這個叫樹上啟發式合并呢？其實，求解的過程可以看作是輕兒子不斷往重兒子合并的過程，這和正常的啟發式合并是一緻的。從這個角度來看，複雜度也是 O ( n l o g n ) O(nlogn) O(nlogn)。
代碼如下
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
int x, f = 1;
char ch;
while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
return x * f;
}
struct node{
int a, b, n;
}d[N * 2];
int fa[N], siz[N], son[N], h[N], v[N], cnt;
int tot[N], Son, maxn;
LL ans[N], sum;
void cr(int a, int b){
d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs1(int a){
int i, b;
siz[a] = 1;
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b == fa[a]) continue;
fa[b] = a;
dfs1(b);
siz[a] += siz[b];
if(siz[b] >= siz[son[a]]) son[a] = b;//找到重兒子
}
}
void add(int a, int c){//周遊 a 的子樹，求出 ans[a]
int i, b;
tot[v[a]] += c;//更新 tot 數組
if(maxn < tot[v[a]]) maxn = tot[v[a]], sum = v[a];
else if(maxn == tot[v[a]]) sum += v[a];//這一步是在更新 sum 和 maxn
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b == fa[a] || b == Son) continue;//遇到重兒子就return，是以隻周遊輕兒子
add(b, c);
}
}
void dsu(int a, int flag){
int i, b;
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b != fa[a] && b != son[a]) dsu(b, 1);//先求輕兒子
}
if(son[a]) dsu(son[a], 0), Son = son[a]; //再求重兒子
add(a, 1); Son = 0; ans[a] = sum;//求出 ans[a]，同時把重兒子标記去除（沒去除的話無法清空 tot 數組
if(flag) add(a, -1), sum = 0, maxn = 0;//如果目前節點是輕兒子，就清空 tot 數組并且重置 sum 和 maxn
}
int main(){
int i, j, n, m, a, b;
n = read();
for(i = 1; i <= n; i++) v[i] = read();
for(i = 1; i < n; i++){
a = read(); b = read();
cr(a, b); cr(b, a);
}
dfs1(1);
dsu(1, 0);
for(i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}