知识前驱：树链剖分
题意：给出一个树，求出每个节点的子树中出现次数最多的颜色的编号和
分析：递归求解，对于一棵树，求出他的所有子树的颜色编号次数加上它本身，找到最大即是它的答案。对于他的兄弟来说，应该将计数器清0并同过程求解，在最后一个兄弟计算完毕后，此时计数器可不清0，再次统计该兄弟的兄弟（即该兄弟的同深度其他节点），便求出了它的父亲的所有子树的颜色编号次数，再加上它本身，找到最大即是它父亲的答案。
dsu on tree在这样一个暴力的过程中，将重儿子作为上述的最后一个兄弟，此时计数器不清0，再暴力统计轻儿子以获得答案。
1 #pragma GCC optimize(3, "Ofast", "inline") 2 3 #include <bits/stdc++.h> 4 5 #define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 6 #define ll long long 7 #define LL long long 8 #define uu unsigned int 9 #define int ll 10 #define ls st<<1 11 #define rs st<<1|1 12 using namespace std; 13 const int maxn = (ll) 1e6 + 5; 14 const int mod = 1000000007; 15 const int inf = 0x3f3f3f3f; 16 17 int son[maxn], siz[maxn], cnt[maxn], col[maxn], ans[maxn]; 18 vector<int> v[maxn]; 19 20 void dfs(int x, int pre) { 21 siz[x] = 1; 22 for (auto &to:v[x]) { 23 if (to == pre) 24 continue; 25 dfs(to, x); 26 siz[x] += siz[to]; 27 if (siz[to] > siz[son[x]]) 28 son[x] = to; 29 } 30 } 31 32 int sum, maxx, now; 33 34 void add(int x, int pre, int val) { 35 cnt[col[x]] += val; 36 if (cnt[col[x]] > maxx) { 37 maxx = cnt[col[x]]; 38 sum = col[x]; 39 } else if (cnt[col[x]] == maxx) 40 sum += col[x]; 41 for (auto &to:v[x]) { 42 if (to == now || to == pre) 43 continue; 44 add(to, x, val); 45 } 46 } 47 48 void dfs2(int x, int pre, bool ord) { 49 for (auto &to:v[x]) { 50 if (to == pre || to == son[x]) 51 continue; 52 dfs2(to, x, false); 53 } 54 if (son[x]) { 55 dfs2(son[x], x, true); 56 now = son[x]; 57 } 58 add(x, pre, 1); 59 ans[x] = sum; 60 if (!ord) { 61 now = 0; 62 add(x, pre, -1); 63 sum = 0; 64 maxx = 0; 65 } 66 } 67 68 signed main() { 69 start; 70 int n; 71 cin >> n; 72 for (int i = 1; i <= n; ++i) 73 cin >> col[i]; 74 for (int i = 1; i < n; ++i) { 75 int x, y; 76 cin >> x >> y; 77 v[x].push_back(y); 78 v[y].push_back(x); 79 } 80 dfs(1, 0); 81 dfs2(1, 0, 0); 82 for (int i = 1; i <= n; ++i) 83 cout << ans[i] << ' '; 84 return 0; 85 }