CF600E Lomsat gelral

题意翻译

一棵树有n个结点,每个结点都是一种颜色,每个颜色有一个编号,求树中每个子树的最多的颜色编号的和。

题目描述

You are given a rooted tree with root in vertex $ 1 $ . Each vertex is coloured in some colour.

Let's call colour $ c $ dominating in the subtree of vertex $ v $ if there are no other colours that appear in the subtree of vertex $ v $ more times than colour $ c $ . So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex $ v $ is the vertex $ v $ and all other vertices that contains vertex $ v $ in each path to the root.

For each vertex $ v $ find the sum of all dominating colours in the subtree of vertex $ v $ .

输入格式

p>The first line contains integer $ n $ ( $ 1\le n\le10^{5} $ ) — the number of vertices in the tree. The second line contains $ n $ integers $ c_{i} $ ( $ 1\le c_{i}\le n $ ), $ c_{i} $ — the colour of the $ i $ -th vertex. Each of the next $ n-1 $ lines contains two integers $ x_{j},y_{j} $ ( $ 1\le x_{j},y_{j}\le n $ ) — the edge of the tree. The first vertex is the root of the tree.

输出格式

Print $ n $ integers — the sums of dominating colours for each vertex.

样例输入

4
1 2 3 4
1 2
2 3
2 4

样例输出

10 9 3 4

分析

此题做法很多,比如先dfs序转成序列问题,然后主席树/线段树合并/莫队搞一搞。

本文要讲的是树上启发式合并算法。

考虑暴力做法:对于每个点,dfs它的子树,每个点可以$O(1)$统计答案,复杂度$O(n^2)$。

复杂度高的原因:每次做完就把信息清除掉了,没有重复利用。

树上启发式合并的做法:

首先预处理出每个点的重儿子。对于点$u$先对每个轻儿子递归统计答案,把信息清掉,然后对重儿子递归统计答案,注意重儿子的信息要保留。

现在我们再dfs一次$u$的所有轻子树,把信息合并起来。再把$u$的信息加进去,就是$u$的答案了。

复杂度分析:

如果没有最后一步重新dfs轻子树,那么复杂度是$O(n)$的。所以我们只要计算dfs轻子树的复杂度。

每个点对复杂度的贡献为它到根路径上的轻链条数,即$O(\log n)$。所以总复杂度为$O(n\log n)$。

空间复杂度$O(n)$,非常高效的算法。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 1e5+50;

int n, a[N];

struct Graph {
    struct Edge {
        int to, nxt;
    } e[N<<1];
    int top, head[N];

    Graph(): top(0) {
        memset(head, -1, sizeof head);
    }

    void add(int u, int v) {
        e[top] = (Edge){v, head[u]};
        head[u] = top++;
    }

    void add2(int u, int v) {
        add(u, v);
        add(v, u);
    }
} G;

int siz[N], son[N];
ll sum[N];
int cnt[N], maxCnt;
ll ans[N];

void dfs1(int u, int fa) {
    siz[u] = 1;
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (!son[u] || siz[v] > siz[son[u]])
            son[u] = v;
    }
}

void change(int u, int val) {
    int c = a[u];
    sum[cnt[c]] -= c;
    cnt[c] += val;
    sum[cnt[c]] += c;
    if (sum[maxCnt+1]) maxCnt++;
    if (!sum[maxCnt]) maxCnt--;
}

void update(int u, int fa, int val) {
    change(u, val);
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa) continue;
        update(v, u, val);
    }
}

void dfs2(int u, int fa, bool keep) {
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa || v == son[u]) continue;
        dfs2(v, u, false);
    }

    if (son[u]) dfs2(son[u], u, true);

    change(u, 1);
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa || v == son[u]) continue;
        update(v, u, 1);
    }

    ans[u] = sum[maxCnt];

    if (!keep) update(u, fa, -1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G.add2(u, v);
    }
    dfs1(1, 0);
    dfs2(1, 0, false);
    for (int i = 1; i <= n; i++)
        printf("%I64d ", ans[i]);
    puts("");
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论