CF600E Lomsat gelral

首先考虑暴力，对于每一个点 $u$ ，将每个子树的颜色统计上，并更新答案，对于每一个节点都需要便利所有子树，复杂的为 $O(n^2)$ 。但是我们可以发现，在计算一个点时，可以选择一个儿子将其信息直接拿过来，选择节点个数最多的子树显然是最快的。

所以我们得到了启发式合并的策略：

对于每一个节点：

递归搜索所有轻儿子，完成后清空；
搜索重儿子，完成后不清空；
搜索所有的轻儿子，将信息叠上；
即得到了该点的答案。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 2e5 + 10;
LL mx, sum, ans[N];
int n, c[N], cnt[N];
int p[N], sz[N], son[N];
int idx, hd[N], nxt[M], edg[M];
void dfs1(int x)
{
    sz[x] = 1;
    son[x] = -1;
    for (int i = hd[x]; ~i; i = nxt[i])
    {
        if (p[edg[i]])
            continue;
        p[edg[i]] = x;
        dfs1(edg[i]);
        sz[x] += sz[edg[i]];
        if (son[x] == -1 || sz[edg[i]] > sz[son[x]])
            son[x] = edg[i];
    }
}
void update(int x, int op, int avoid)
{
    cnt[c[x]] += op;
    if (cnt[c[x]] > mx)
    {
        mx = cnt[c[x]];
        sum = c[x];
    }
    else if (cnt[c[x]] == mx)
        sum += c[x];
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != avoid && edg[i] != p[x])
            update(edg[i], op, avoid);
}
void dfs2(int x, int op)
{
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != son[x] && edg[i] != p[x])
            dfs2(edg[i], 0);
    if (~son[x])
        dfs2(son[x], 1);
    update(x, 1, son[x]);
    ans[x] = sum;
    if (!op)
    {
        update(x, -1, 0);
        sum = mx = 0;
    }
}
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1, a, b; i < n; i++)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    p[1] = -1;
    dfs1(1);
    dfs2(1, 1);
    for (int i = 1; i <= n; i++)
        printf("%lld ", ans[i]);
    return 0;
}