CF600E 【Lomsat gelral】

发表于 | 更新于 | 分类于 ，

$\Large\mathscr{D}\mathcal{escription}$

给定一颗 $n$ 节点的树，每个节点都有一种颜色。求每个子树中出现次数最多的颜色的编号和。

$\Large\mathscr{S}\mathcal{olution}$

这里介绍两种方法。

法一 $:$ $Dsu$ $on$ $Tree$

$\qquad$ 先放一下大佬的博客 $:$ $Dsu$ $on$ $Tree$ 入门

$\qquad$ 模板题。

$\qquad$ 直接走流程 $:$

  • 先剖出轻重链。
  • $Dfs$ 遍历节点。
  • 先递归所有轻儿子，同时消除影响。
  • 再递归重儿子，不消除影响。
  • 统计所有轻儿子的贡献。并更新该节点答案。
  • 删去所有轻儿子的贡献。

$\qquad$ 复杂度 $:$ $\mathcal{O}(n log_n)$

$\qquad$ 简单证明 $:$ 每个点到根的路径上轻边个数不会超过 $log_n$ 条。所以每个点被作为轻边访问到的次数不会超过 $log_n$ 次。所以复杂度是 $\mathcal{O}(n log_n)$。

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
// Dsu on Tree
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e5 + 7;

int Head[N], Cnt = 0;

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

inline void Add_edge(int x, int y) {
    e[++Cnt] = (Edge) {y, Head[x]}, Head[x] = Cnt;
}

int Col[N], Siz[N], Son[N];

inline void Dfs1(int x, int last) {
    Siz[x] = 1;
    for (int i = Head[x]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == last) continue;
        Dfs1(v, x);
        Siz[x] += Siz[v];
        if (Siz[v] > Siz[Son[x]]) Son[x] = v;
    }
}

int Max, Wson, Tot[N];
long long Sum, Ans[N];

inline void Update(int x, int last, int k) {
    Tot[Col[x]] += k;
    if (Tot[Col[x]] > Max) Max = Tot[Col[x]], Sum = Col[x];
    else if (Tot[Col[x]] == Max) Sum += Col[x];
    for (int i = Head[x]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == last || v == Wson) continue;
        Update(v, x, k);
    }
}

inline void Dfs2(int x, int last, int opt) {
    for (int i = Head[x]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == last || v == Son[x]) continue;
        Dfs2(v, x, 0);
    }
    if (Son[x]) Dfs2(Son[x], x, 1), Wson = Son[x];
    Update(x, last, 1);
    Wson = 0;
    Ans[x] = Sum;
    if (!opt) Update(x, last, -1), Max = Sum = 0;
}

int main() {
    int n;
    read(n);
    for (int i = 1; i <= n; ++i) read(Col[i]);
    for (int i = 1; i < n; ++i) {
        int x, y;
        read(x), read(y);
        Add_edge(x, y), Add_edge(y, x);
    }
    Dfs1(1, 0);
    Dfs2(1, 0, 0);
    for (int i = 1; i <= n; ++i) printf("%lld ", Ans[i]);
    return 0;
}

法二 $:$ 线段树合并

$\qquad$ 对于每个节点开一颗动态开点的权值线段树。维护单种颜色出现最多的次数和出现次数最多的颜色的编号和。

$\qquad$ 然后 $Dfs$ 就行了。递归到点 $u$ 时，把他的每一个儿子 $v$ 的线段树与自己合并起来。直接更新答案。

$\qquad$ 复杂度 $:$ $\mathcal{O}(n log_n)$

$\qquad$ 较 $Dsu$ $on$ $Tree$ 的缺点 $:$ 空间要开 $nlog_n$ 

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
90
91
92
93
94
95
96
97
98
99
100
// 线段树合并
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e5 + 7;

int Head[N], Cnt = 0;

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

inline void Add_edge(int x, int y) {
    e[++Cnt] = (Edge) {y, Head[x]}, Head[x] = Cnt;
}

int Col[N], Root[N], n;
long long Ans[N];

struct Node {
    int max, ls, rs;
    long long val;
    #define Max(x) Tre[x].max
    #define Val(x) Tre[x].val
    #define ls(x) Tre[x].ls
    #define rs(x) Tre[x].rs
};

struct Segment_Tree {
    Node Tre[N * 20];
    int Cnt = 0;
    inline void Pushup(int p) {
        int L = ls(p), R = rs(p);
        if (Max(L) < Max(R)) std::swap(L, R);
        Max(p) = Max(L), Val(p) = Val(L);
        if (Max(L) == Max(R)) Val(p) += Val(R);
    }
    inline void Build(int &p, int l, int r, int k) {
        if (!p) p = ++Cnt;
        if (l == r) {
            Max(p) = 1;
            Val(p) = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (k <= mid) Build(ls(p), l, mid, k);
        else Build(rs(p), mid + 1, r, k);
        Pushup(p);
    }
    inline int Merge(int x, int y, int l, int r) {
        if (!x || !y) return x | y;
        if (l == r) {
            Max(x) += Max(y);
            return x;
        }
        int mid = (l + r) >> 1;
        ls(x) = Merge(ls(x), ls(y), l, mid);
        rs(x) = Merge(rs(x), rs(y), mid + 1, r);
        Pushup(x);
        return x;
    }
};
Segment_Tree T;

inline void Dfs(int x, int last) {
    for (int i = Head[x]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == last) continue;
        Dfs(v, x);
        Root[x] = T.Merge(Root[x], Root[v], 1, n);
    }
    Ans[x] = T.Val(Root[x]);
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(Col[i]);
    for (int i = 1; i < n; ++i) {
        int x, y;
        read(x), read(y);
        Add_edge(x, y), Add_edge(y, x);
    }
    for (int i = 1; i <= n; ++i) T.Build(Root[i], 1, n, Col[i]);
    Dfs(1, 0);
    for (int i = 1; i <= n; ++i) printf("%lld ", Ans[i]);
    return 0;
}