知识前驱：树链剖分

codeforces600E. Lomsat gelral

题意：给出一个树，求出每个节点的子树中出现次数最多的颜色的编号和

分析：递归求解，对于一棵树，求出他的所有子树的颜色编号次数加上它本身，找到最大即是它的答案。对于他的兄弟来说，应该将计数器清0并同过程求解，在最后一个兄弟计算完毕后，此时计数器可不清0，再次统计该兄弟的兄弟（即该兄弟的同深度其他节点），便求出了它的父亲的所有子树的颜色编号次数，再加上它本身，找到最大即是它父亲的答案。

dsu on tree在这样一个暴力的过程中，将重儿子作为上述的最后一个兄弟，此时计数器不清0，再暴力统计轻儿子以获得答案。

1 #pragma GCC optimize(3, "Ofast", "inline")
2
3 #include
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 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 }