跳转至

CF600E

知识点

  • dsu on tree

题意简述

给定一棵大小为 \(n\) 的一棵树,每个结点都有一个颜色 \(c_i\),每种颜色有一个编号,求树中每个子树的最多的颜色 编号 的和1

数据范围:\(1 \le n, c_i \le 10^5\)

解题思路

\(\textrm{occ}(i)\) 表示颜色 \(i\) 出现的次数。

在处理每个并列的子树时,我们发现每次要清空一次 \(\textrm{occ}\),这很浪费时间;

但最后一个子树的 \(\textrm{occ}\) 不需要清空,可以直接贡献到父亲节点上去。

考虑 dsu on tree,我们不清空的重儿子所在的子树,直接合并到父亲节点上。


分析时间复杂度,一个节点被暴力清空,只可能因为它的某个祖先是轻儿子。

而每条轻链上的节点个数是 \(O(\log n)\) 的,于是总复杂度为 \(O(n\log n)\)

代码实现

核心部分已用高亮标出。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define LL long long

const int N = 1e5 + 5;
const int M = 2e5 + 5;

int n, c[N], cnt, first[N];
int son[N], occ[N], siz[N], maxocc;
LL sum, ans[N];

struct EDGE {
    int to, _next;
} e[M];

void add(int u, int v) {
    e[cnt].to = v, e[cnt]._next = first[u];
    first[u] = cnt++;
}

void dfs1(int x, int p) {
    siz[x] = 1;
    for(int i = first[x]; ~i; i = e[i]._next) {
        int y = e[i].to;
        if(y == p)
            continue;
        dfs1(y, x);
        siz[x] += siz[y];
        if(siz[y] > siz[son[x]])
            son[x] = y;
    }
}

void clear(int x, int p) {
    --occ[c[x]];
    for(int i = first[x]; ~i; i = e[i]._next) {
        int y = e[i].to;
        if(y == p)
            continue;
        clear(y, x);
    }
}

void calc(int x, int p, int g) {
    ++occ[c[x]];
    if(occ[c[x]] > maxocc) {
        maxocc = occ[c[x]];
        sum = c[x];
    }
    else if(occ[c[x]] == maxocc)
        sum += c[x];
    for(int i = first[x]; ~i; i = e[i]._next) {
        int y = e[i].to;
        if(y == p || y == g)
            continue;
        calc(y, x, g);
    }
}

void dfs2(int x, int p) {
    for(int i = first[x]; ~i; i = e[i]._next) {
        int y = e[i].to;
        if(y == p || y == son[x])
            continue;
        dfs2(y, x);
        clear(y, x);
        sum = maxocc = 0;
    }
    if(son[x])
        dfs2(son[x], x);
    calc(x, p, son[x]);
    ans[x] = sum;
}

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

  1. 原题链接: E. Lomsat gelral