$\LARGE{题目描述}$

给定一棵树，对于每一个节点 $u$，求其子树中所有点的某个属性（如不同的颜色数）。

$\LARGE{分析}$

如果对于每一个节点，合并其子树的复杂度为 $O(n ^ 2)$ 。

考虑启发式合并，定义 $u$ 的儿子节点中，子树的节点数最大的为 $u$ 的重儿子 （和树链剖分中一样）。

$dfs$ 节点 $u$ ，先递归求出 $u$ 的非重儿子节点子树上的节点的答案，再递归出重儿子的答案，并保存下来，

最后将 $u$ 的非重儿子子树合并进答案，就能计算出 $u$ 的答案。

$\LARGE{时间复杂度分析}$

对于每一个节点 $v$ ，它会被再次加入当且仅当 $dfs$ 的点 $u$ 满足：

• $u$ 为 $v$ 的祖先节点

• $u$ 到 $v$ 的路径上第一条边为轻边

由于根节点到任何节点的路径上轻边数量为 $O(\log n)$ ，所以总复杂度为 $O(n\log n)$ 。

$\LARGE{实现}$

以 $\textrm{CF600E Lomsat gelral}$ 为例（可以根据代码理解）。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10; 
int n;
int c[N];
int h[N], e[N], ne[N], idx;
int l[N], r[N], id[N], tot;
int p[N], sz[N], son[N], cnt[N], Maxn;
long long ans[N], colors;
bool vis[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u, int fa) {
    l[u] = ++ tot, id[tot] = u;
    p[u] = fa, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == fa) continue;
        dfs1(ver, u);
        sz[u] += sz[ver];
        if (sz[ver] > sz[son[u]]) son[u] = ver;
    }
    r[u] = ++ tot, id[tot] = u;
}

void dfs2 (int u, bool keep) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver != p[u] && ver != son[u])
            dfs2(ver, 0);
    }
    if (son[u]) dfs2(son[u], 1);
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver != p[u] && ver != son[u]) {
            for (int j = l[ver]; j <= r[ver]; j ++ ) {
                if (vis[id[j]]) continue;
                vis[id[j]] = true, cnt[c[id[j]]] ++ ;
                if (cnt[c[id[j]]] > Maxn) Maxn = cnt[c[id[j]]], colors = c[id[j]];
                else if (cnt[c[id[j]]] == Maxn) colors += c[id[j]];
            }
        }
    }
    vis[u] = true, cnt[c[u]] ++ ;
    if (cnt[c[u]] > Maxn) Maxn = cnt[c[u]], colors = c[u];
    else if (cnt[c[u]] == Maxn) colors += c[u];
    ans[u] = colors;
    if (!keep) {
        for (int i = l[u]; i <= r[u]; i ++ ) {
            vis[id[i]] = false;
            cnt[c[id[i]]] = 0;
        }
        Maxn = 0, colors = 0;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++ ) printf("%lld ", ans[i]);
    return 0;
}