2025 Summer Day5

Content: Problem on Tree

Date：2025.7.21

概览

树的重心
树上启发式合并
树链剖分
左偏树
点分治

具体内容

树的重心

定义

树的重心是满足如下条件的点 $u$ :

树上不存在其他节点 $v$ ，使得 $\max\{\operatorname{siz}(son_v)\} < \max\{\operatorname{size}(son_u)\}$ 。

性质

树的重心 $G$ 有如下性质：

当以 $G$ 为根节点时，不能存在 $v$ 满足 $\max_{\forall v \in \operatorname{son}(u)}\{\operatorname{size}(v)\} > \frac{N}{2}$ ( $N$ 为整棵树的大小)。反之亦然。
树中所有节点到 $G$ 的距离之和最小，如果有两个重心，则距离相同。
如果两棵树的重心分别为 $G_1$ ， $G_2$ ，则两棵树由一条边拼接起来之后，新树的重心一定在 $G_1$ 到 $G_2$ 的路径上。
在一棵树上加入 (或删除) 一个叶子节点，其重心只移动一条边的距离。
树的重心一定在以根节点为链头的重链上。

例题

CF685B Kay and Snowflake

题目大意：

求一颗大小为 $n$ ( $1 \le n \le 10^{5}$ ) 有根树的所有子树的重心。

考虑运用性质 $4$ ，对整棵树进行 $dfs$ ，每次用子节点的重心暴力向上跳，再用性质 $1$ 检查，复杂度 $\Theta(n \log n)$ 。

Code

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int N = 3e5 + 5;
6
int head[N], cnt = 0;
7
int n, q, father[N], query_node;
8
int son[N], sub_size[N], answer[N];
9

10
struct Edge {
11
  int to, next;
12
} e[N << 1];
13

14
void add_edge(const int u, const int v) {
15
  e[cnt].to = v;
16
  e[cnt].next = head[u];
17
  head[u] = cnt++;
18
}
19

20
void dfs(const int u) {
21
  sub_size[u] = 1;
22

23
  for (int i = head[u]; ~i; i = e[i].next) {
24
    const int v = e[i].to;
25
    if (v == father[u]) continue;
26

27
    dfs(v);
28
    sub_size[u] += sub_size[v];
29

30
    if (son[u] == 0 || sub_size[v] > sub_size[son[u]]) {
31
      son[u] = v;
32
    }
33
  }
34

35
  if (son[u] == 0) {
36
    answer[u] = u;
37
  } else {
38
    answer[u] = answer[son[u]];
39

40
    while (answer[u] != u) {
41
      if (sub_size[son[answer[u]]] * 2 <= sub_size[u] && (sub_size[u] - sub_size[answer[u]]) * 2 <= sub_size[u]) {
42
        break;
43
      }
44
      answer[u] = father[answer[u]];
45
    }
46
  }
47
}
48

49
int main() {
50
  ios::sync_with_stdio(false);
51
  cin.tie(nullptr);
52
  cout.tie(nullptr);
53

54
  memset(head, -1, sizeof(head));
55

56
  cin >> n >> q;
57

58
  for (int i = 2; i <= n; i++) {
59
    cin >> father[i];
60
    add_edge(i, father[i]);
61
    add_edge(father[i], i);
62
  }
63

64
  dfs(1);
65

66
  while (q--) {
67
    cin >> query_node;
68
    cout << answer[query_node] << '\n';
69
  }
70

71
  return 0;
72
}

树上启发式合并

算法内容

对于某些问题，暴力的复杂度远远大于 $std$ 的复杂度，我们可以考虑启发式合并的思想。启发式合并时人类对于算法的主观优化，我们以按秩合并的并查集为例。

并查集

1
struct DSU {
2
    int father[N], size[N];
3
    void init(int limit) {
4
        std::iota(father + 1, father + n + 1, 1);
5
        std::memset(size, 1, sizeof(size));
6
    }
7

8
    int find(int x) {
9
        if (father[x] != x) father[x] = find(father[x]);
10
        return father[x];
11
    }
12

13
    bool check(int x, int y) {
14
        return find(x) == find(y);
15
    }
16

17
    void merge(int x, int y) {
18
        x = find(x), y = find(y);
19
        if (x == y) return void();
20

21
        // 按秩合并
22
        if (size[x] > size[y]) {
23
            swap(x, y);
24
        }
25

26
        father[x] = y;
27
    }
28
}

通过人的主观感受，我们可以知道将大小更小的子树合并到大小更大的子树上一定是更优的。树上启发式合并也是这种思想。我们通过和树链剖分类似的方法，将子节点分为重儿子和轻儿子，对于统计答案时，我们对重儿子统计的答案保留，对轻儿子统计的答案进行撤销，这样保证了复杂度的正确性。

例题

CF600E Lomsat gelral

题目描述 给定一个有根树，每个点有一个颜色 $c_i$ ，对每个子树，求所有出现最多的颜色的和。 $n \le 10^{5}$

我们开一个桶记录每一种颜色再子树内的出现次数，并同时维护两个变量：

$max$ ：当前出现最多的颜色出现的次数。
$sum$ ：出现最多的颜色的和。

每次我们遍历的时候先遍历轻儿子，再遍历重儿子，传入一个标记 $f$ ，表示当前的统计数据是否保留，并根据题意维护 $max$ 和 $sum$ 即可。

Code

1
#include <bits/stdc++.h>
2

3
using std::cin;
4
using std::cout;
5

6
constexpr int N = 1e5 + 5;
7
int head[N], cnt = 0;
8
int n, col[N], u, v;
9
int tot[N], size[N], son[N], father[N], dfn = 0;
10
long long max = 0, sum = 0, answer[N];
11

12
class Edge {
13
public:
14
    int to, next;
15

16
    Edge(const int to = 0, const int next = 0) : to(to), next(next) {}
17
} e[N << 1];
18

19
void add_edge(const int u, const int v) {
20
    e[cnt] = Edge(v, head[u]);
21
    head[u] = cnt++;
22
}
23

24
void dfs1(const int u, const int fa) {
25
    size[u] = 1;
26
    father[u] = fa;
27

28
    for (int i = head[u]; ~i; i = e[i].next) {
29
        int v = e[i].to;
30
        if (v == fa) continue;
31

32
        dfs1(v, u);
33
        size[u] += size[v];
34

35
        if (son[u] == 0 || size[v] > size[son[u]]) {
36
            son[u] = v;
37
        }
38
    }
39
}
40

41
void update(const int u, const int val, const int ban) {
42
    tot[col[u]] += val;
43
    if (tot[col[u]] == max) {
44
        sum += col[u];
45
    } else if (tot[col[u]] > max) {
46
        max = tot[col[u]];
47
        sum = col[u];
48
    }
49

50
    for (int i = head[u]; ~i; i = e[i].next) {
51
        const int v = e[i].to;
52
        if (v == father[u] || v == ban) {
53
            continue;
54
        }
55

56
        update(v, val, ban);
57
    }
58
}
59

60
void dfs2(const int u, const bool heavy_son) {
61
    for (int i = head[u]; ~i; i = e[i].next) {
62
        const int v = e[i].to;
63
        if (v == father[u] || v == son[u]) {
64
            continue;
65
        }
66

67
        dfs2(v, false);
68
    }
69

70
    if (son[u] != 0) {
71
        dfs2(son[u], true);
72
    }
73

74
    update(u, 1, son[u]);
75

76
    answer[u] = sum;
77

78
    if (heavy_son == false) {
79
        update(u, -1, -1);
80
        sum = 0;
81
        max = 0;
82
    }
83
}
84

85
int main() {
86
    std::ios::sync_with_stdio(false);
87
    cin.tie(nullptr);
88
    cout.tie(nullptr);
89

90
    std::memset(head, -1, sizeof(head));
91

92
    cin >> n;
93

94
    for (int i = 1; i <= n; i++) {
95
        cin >> col[i];
96
    }
97

98
    for (int i = 1; i < n; i++) {
99
        cin >> u >> v;
100
        add_edge(u, v);
101
        add_edge(v, u);
102
    }
103

104
    dfs1(1, 0);
105
    dfs2(1, true);
106

107
    for (int i = 1; i <= n; i++) {
108
        cout << answer[i] << " ";
109
    }
110

111
    return 0;
112
}

树链剖分

算法步骤

我们维护 $5$ 个数组：

$fa[u]$ ：表示节点 $u$ 的父亲。
$size[u]$ ：表示节点 $u$ 的子树大小。
$son[u]$ ：表示节点 $u$ 的重儿子 (即节点 $u$ 的子节点中子树大小最大的节点) 的编号。
$top[u]$ ：表示节点 $u$ 所在链的链头编号。
$id[i]$ ：表示 $dfn$ 值为 $i$ 的节点编号。

这样我们就把整棵树拆成了若干条链和轻边。这样我们就可以用线段树对整棵树进行维护 (每一条链都对应了一段连续的 $dfn$ 区间)。

例题

洛谷 P3384 重链剖分/树链剖分

根据题意对树剖完了的 $dfn$ 序列用线段树维护即可。

Code

1
#include <bits/stdc++.h>
2
#define OnlineJudge
3

4
using std::cin;
5
using std::cout;
6

7
constexpr int N = 1e5 + 5;
8
int head[N], cnt = 0;
9
int n, m, root, P, u, v, initial_value[N], value[N], opt;
10
int top[N], size[N], son[N], dep[N], fa[N], id[N], num = 0;
11

12
class Edge {
13
public:
14
    int to, next;
15

16
    Edge(const int to = 0, const int next = 0) : to(to), next(next) {}
17
} e[N << 1];
18

19
void add_edge(int u, int v) {
20
    e[cnt] = Edge(v, head[u]);
21
    head[u] = cnt++;
22
}
23

24
struct SegmentTree {
25
    struct Node {
26
        int left, right;
27
        long long sum, add;
28

29
        explicit Node(const int l = 0, const int r = 0, const int s = 0, const int a = 0) :
30
            left(l), right(r), sum(s), add(a) {}
31
    };
32

33
    Node tr[N << 2];
34

35
    SegmentTree() {}
36

37
    void make_lazy(const int k, const long long value) {
38
        (tr[k].sum += (tr[k].right - tr[k].left + 1) * value) %= P;
39
        (tr[k].add += value) %= P;
40
    }
41

42
    void push_up(const int k) {
43
        const int left_child = k << 1, right_child = k << 1 | 1;
44
        tr[k].sum = tr[left_child].sum + tr[right_child].sum;
45
        tr[k].sum %= P;
46
    }
47

48
    void push_down(const int k) {
49
        if (tr[k].add == 0) return void();
50

51
        const int left_child = k << 1, right_child = k << 1 | 1;
52
        make_lazy(left_child, tr[k].add);
53
        make_lazy(right_child, tr[k].add);
54

55
        tr[k].add = 0;
56
    }
57

58
    void build_tree(const int k, const int left, const int right) {
59
        tr[k] = Node(left, right);
60

61
        if (tr[k].left == tr[k].right) {
62
            tr[k].sum = value[left] % P;
63
            return void();
64
        }
65

66
        const int mid = (tr[k].left + tr[k].right) >> 1;
67
        const int lc = k << 1, rc = k << 1 | 1;
68

69
        build_tree(lc, left, mid);
70
        build_tree(rc, mid + 1, right);
71

72
        push_up(k);
73
    }
74

75
    void modify(const int k, const int left, const int right, const long long value) {
76
        if (tr[k].left >= left && tr[k].right <= right) {
77
            make_lazy(k, value);
78
            return void();
79
        }
80

81
        push_down(k);
82

83
        const int mid = (tr[k].left + tr[k].right) >> 1;
84
        const int lc = k << 1, rc = k << 1 | 1;
85

86
        if (right <= mid) {
87
            modify(lc, left, right, value);
88
        } else if (left > mid) {
89
            modify(rc, left, right, value);
90
        } else {
91
            modify(lc, left, mid, value);
92
            modify(rc, mid + 1, right, value);
93
        }
94

95
        push_up(k);
96
    }
97

98
    long long query(const int k, const int left, const int right) {
99
        if (tr[k].left >= left && tr[k].right <= right) {
100
            return tr[k].sum % P;
101
        }
102

103
        push_down(k);
104

105
        const int mid = (tr[k].left + tr[k].right) >> 1;
106
        const int lc = k << 1, rc = k << 1 | 1;
107

108
        if (right <= mid) {
109
            return query(lc, left, right) % P;
110
        }
111
        if (left > mid) {
112
            return query(rc, left, right) % P;
113
        }
114
        return (query(lc, left, mid) + query(rc, mid + 1, right)) % P;
115
    }
116
} seg;
117

118
void dfs(int u, int father) {
119
    fa[u] = father;
120
    size[u] = 1;
121
    dep[u] = dep[father] + 1;
122

123
    for (int i = head[u]; ~i; i = e[i].next) {
124
        int v = e[i].to;
125
        if (v == father) {
126
            continue;
127
        }
128

129
        dfs(v, u);
130
        size[u] += size[v];
131
        if (son[u] == 0 || size[v] > size[son[u]]) {
132
            son[u] = v;
133
        }
134
    }
135
}
136

137
void dfs2(int u, int link_top) {
138
    top[u] = link_top;
139
    id[u] = ++num;
140
    value[num] = initial_value[u];
141

142
    if (son[u] == 0) return;
143

144
    dfs2(son[u], link_top);
145

146
    for (int i = head[u]; ~i; i = e[i].next) {
147
        int v = e[i].to;
148
        if (v == fa[u] || v == son[u]) {
149
            continue;
150
        }
151

152
        dfs2(v, v);
153
    }
154
}
155

156
using std::swap;
157

158
void update_range(int u, int v, const long long value) {
159
    while (top[u] != top[v]) {
160
        #ifndef OnlineJudge
161
        cout << u << ' ' << top[u] << " " << v << " " << top[v] << '\n';
162
        #endif
163

164
        if (dep[top[u]] < dep[top[v]]) {
165
            swap(u, v);
166
        }
167

168
        seg.modify(1, id[top[u]], id[u], value);
169
        u = fa[top[u]];
170
    }
171

172
    if (dep[u] > dep[v]) {
173
        swap(u, v);
174
    }
175
    seg.modify(1, id[u], id[v], value);
176
}
177

178
long long query_range(int u, int v) {
179
    long long retval = 0;
180

181
    while (top[u] != top[v]) {
182
        if (dep[top[u]] < dep[top[v]]) {
183
            swap(u, v);
184
        }
185

186
        (retval += seg.query(1, id[top[u]], id[u])) %= P;
187
        u = fa[top[u]];
188
    }
189

190
    if (dep[u] > dep[v]) {
191
        swap(u, v);
192
    }
193
    (retval += seg.query(1, id[u], id[v])) %= P;
194

195
    return retval;
196
}
197

198
void update_subtree(const int u, const long long value) {
199
    seg.modify(1, id[u], id[u] + size[u] - 1, value);
200
}
201

202
long long query_subtree(const int u) {
203
    return seg.query(1, id[u], id[u] + size[u] - 1);
204
}
205

206
using std::cin;
207
using std::cout;
208

209
int main() {
210
    std::ios::sync_with_stdio(false);
211
    cin.tie(nullptr);
212
    cout.tie(nullptr);
213

214
    std::memset(head, -1, sizeof(head));
215

216
    cin >> n >> m >> root >> P;
217

218
    for (int i = 1; i <= n; i++) {
219
        cin >> initial_value[i];
220
    }
221

222
    for (int i = 1; i < n; i++) {
223
        cin >> u >> v;
224

225
        add_edge(u, v);
226
        add_edge(v, u);
227
    }
228

229
    dfs(root, 0);
230
    dfs2(root, root);
231

232
    seg.build_tree(1, 1, n);
233

234
    for (int i = 1; i <= m; i++) {
235
        cin >> opt;
236

237
        switch (opt) {
238
            int x, y;
239
            long long z;
240

241
            case 1:
242
                cin >> x >> y >> z;
243
                update_range(x, y, z);
244
                break;
245
            case 2:
246
                cin >> x >> y;
247
                cout << query_range(x, y) << '\n';
248
                break;
249
            case 3:
250
                cin >> x >> z;
251
                update_subtree(x, z);
252
                break;
253
            case 4:
254
                cin >> x;
255
                cout << query_subtree(x) << '\n';
256
                break;
257
            default:
258
                break;
259
        }
260
    }
261

262
    return 0;
263
}

左偏树

左偏树是可并堆的一种。

定义

我们定义 外节点 表示子节点数小于两个的节点。定义一个节点 $u$ 的 $dist_u$ 表示到最近的外节点的距离。左偏树满足如下性质：

对于任意一个节点 $u$ ，均满足 $dist_{\operatorname{lson}(u)} > dist_{\operatorname{rson}(u)}$ ，即左偏。
由上一条性质我们可以推导出： $dist_u = dist_{\operatorname{rson}(u)} + 1$ 。

操作

合并

左偏树的合并操作有以下几个步骤：

定义 $\operatorname{merge}(x, y)$ 表示将以 $x$ 和 $y$ 为根节点的左偏树合并。
我们钦定 $val_x < val_y$ ，将 $x$ 作为合并后的新的根节点即维护一个小根堆。
接下来进行 $\operatorname{merge}(\operatorname{lson}(x),y)$ 。
然后维护左偏树的性质：
- 如果 $dist_{\operatorname{lson}(x)} < dist_{\operatorname{rson}(x)}$ ，则 $\operatorname{swap}(\operatorname{lson}(x), \operatorname{rson}(x))$ 。
- 维护 $dist_x = dist_{\operatorname{rson}(x)} + 1$ 。

删除

删除还是基于左偏树的 $\operatorname{merge}(x,y)$ 操作，如果删除的是 $x$ ，则 $\operatorname{merge}(\operatorname{lson}(x), \operatorname{rson}(x))$ ，然后维护左偏树的性质即可

例题

洛谷 P3337 左偏树/可并堆

模板题，根据题意维护即可。

Code

1
#include <bits/stdc++.h>
2

3
using std::cin;
4
using std::cout;
5

6
constexpr int N = 1e5 + 5;
7
int n, m, erase[N], op, x, y;
8

9
class LeftistTree {
10
public:
11
    struct Node {
12
        int value, index;
13

14
        Node(const int v = 0, const int i = 0) :
15
            value(v), index(i) {}
16

17
        bool operator<(const Node& compare_node) const {
18
            if (value != compare_node.value) {
19
                return value < compare_node.value;
20
            }
21
            return index < compare_node.index;
22
        }
23

24
        bool operator>(const Node& compare_node) const {
25
            if (value != compare_node.value) {
26
                return value > compare_node.value;
27
            }
28
            return index > compare_node.index;
29
        }
30
    } val[N];
31
    int father[N] = {};
32
    int dist[N] = {}, lc[N] = {}, rc[N] = {};
33

34
    int find(const int x) {
35
        if (father[x] != x) father[x] = find(father[x]);
36
        return father[x];
37
    }
38

39
    int merge(int x, int y) {
40
        using std::swap;
41

42
        if (x == 0 || y == 0) return x + y;
43
        if (val[x] > val[y]) swap(x, y);
44

45
        rc[x] = merge(rc[x], y);
46

47
        if (dist[lc[x]] < dist[rc[x]]) swap(lc[x], rc[x]);
48
        dist[x] = dist[rc[x]] + 1;
49

50
        return x;
51
    }
52
} tr;
53

54
int main() {
55
    using std::memset;
56

57
    std::ios::sync_with_stdio(false);
58
    cin.tie(nullptr);
59
    cout.tie(nullptr);
60

61
    memset(tr.rc, 0, sizeof(tr.rc));
62
    memset(tr.lc, 0, sizeof(tr.lc));
63
    memset(tr.dist, 0, sizeof(tr.dist));
64
    tr.dist[0] = -1;
65

66

67
    cin >> n >> m;
68

69
    for (int i = 1; i <= n; i++) {
70
        cin >> tr.val[i].value;
71
        tr.val[i].index = i;
72
        tr.father[i] = i;
73
    }
74

75
    for (int i = 1; i <= m; i++) {
76
        cin >> op;
77

78
        if (op == 1) {
79
            cin >> x >> y;
80

81
            if (erase[x] || erase[y]) {
82
                continue;
83
            }
84

85
            x = tr.find(x), y = tr.find(y);
86
            if (x == y) {
87
                continue;
88
            }
89

90
            tr.father[x] = tr.father[y] = tr.merge(x, y);
91
        } else if (op == 2) {
92
            cin >> x;
93

94
            if (erase[x] == true) {
95
                cout << "-1\n";
96
            } else {
97
                x = tr.find(x);
98
                cout << tr.val[x].value << '\n';
99

100
                erase[x] = true;
101
                const int current_root = tr.merge(tr.lc[x], tr.rc[x]);
102
                tr.father[tr.lc[x]] = current_root;
103
                tr.father[tr.rc[x]] = current_root;
104
                tr.father[x] = current_root;
105
                tr.lc[x] = 0;
106
                tr.rc[x] = 0;
107
                tr.dist[x] = 0;
108
            }
109
        }
110
    }
111

112
    return 0;
113
}

点分治

OI Wiki

思想

我们对每个节点进行分治，将树上的路径分为 经过点 $u$ 的 和 不经过点 $u$ 的，而点 $u$ 通常取树的重心。

典型问题： $K$ 长路径计数。