「SDOI 2017」树点涂色【树链剖分 + 线段树】

Time Limit: 10 Sec Memory Limit: 128 MB

Description

Bob 有一棵 nn 个点的有根树,其中 11 号点是根节点。Bob 在每个节点上涂了颜色,并且每个点上的颜色不同。定义一条路径的权值是,这条路径上的点 (包括起点和终点) 共有多少种不同的颜色。

Bob 可能会进行这几种操作:

  • 1 x1 \ x:把点 xx 到根节点的路径上的所有的点染上一种没有用过的新颜色;
  • 2 x y2 \ x \ y:求 xxyy 的路径的权值;
  • 3 x3 \ x:在以 xx 为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。

Bob 一共会进行 mm 次操作。

Input

第一行两个数 n,mn, m
接下来 n1n - 1 行,每行两个数 a,ba, b,表示 aabb 之间有一条边。
接下来 mm 行,表示操作,格式见题目描述。

Output

每当出现 2,32,3 操作,输出一行:

  • 如果是 22 操作,输出一个数表示路径的权值。
  • 如果是 33 操作,输出一个数表示权值的最大值。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5

Sample Output

1
2
3
4
3
4
2
2

Constraints

1n,m1051 \leqslant n, m \leqslant 10^5

Solution

用树链剖分维护,并在线段树上维护一个节点 xx 到根节点的权值 vxv_x

  • 第一个操作就是树链覆盖,每次在重链上找到一段相同的颜色,暴力在线段树上修改。时间复杂度均摊为 O(logn)O(\log n)
  • 第二个操作就是 vx+vy2vlca(x,y)+1v_x + v_y - 2v_{\text{lca}(x,y)}+1
  • 第三个操作就是线段树区间最值。

时间复杂度为 O(nlog2n)O(n \log^2 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int n, m, p, col_cur, dfn, col_top[maxn << 1], col_bot[maxn << 1], a[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn], top[maxn], tid[maxn];
vector<int> G[maxn];
struct segment_tree {
int l, r, mx, lazy, col;
} tree[maxn << 2];

void dfs1(int x, int f, int d) {
fa[x] = f, dep[x] = d, sz[x] = 1;
for (int i = 0; i < G[x].size(); i++) {
if (G[x][i] != fa[x]) {
dfs1(G[x][i], x, d + 1), sz[x] += sz[G[x][i]];
if (sz[G[x][i]] > sz[son[x]]) son[x] = G[x][i];
}
}
}

void dfs2(int x, int rt) {
top[x] = rt, tid[x] = ++dfn, a[dfn] = x;
if (son[x]) dfs2(son[x], rt);
for (int i = 0; i < G[x].size(); i++) {
if (G[x][i] != fa[x] && G[x][i] != son[x]) {
dfs2(G[x][i], G[x][i]);
}
}
}

void maintain(int k) {
tree[k].mx = max(tree[k << 1].mx, tree[k << 1 | 1].mx);
}

void pushdown(int k) {
if (tree[k].l < tree[k].r && tree[k].lazy) {
tree[k << 1].mx += tree[k].lazy, tree[k << 1].lazy += tree[k].lazy;
tree[k << 1 | 1].mx += tree[k].lazy, tree[k << 1 | 1].lazy += tree[k].lazy;
tree[k].lazy = 0;
}
}

void build(int k, int l, int r) {
tree[k].l = l, tree[k].r = r;
if (l == r) {
tree[k].mx = dep[a[l]], tree[k].col = a[l]; return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
maintain(k);
}

void modify(int k, int l, int r, int v, bool tag) {
if (!tag) pushdown(k);
if (tree[k].l == l && tree[k].r == r) {
if (!tag) tree[k].mx += v, tree[k].lazy += v;
else tree[k].col = v;
return;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
modify(k << 1, l, r, v, tag);
} else if (mid < l) {
modify(k << 1 | 1, l, r, v, tag);
} else {
modify(k << 1, l, mid, v, tag), modify(k << 1 | 1, mid + 1, r, v, tag);
}
if (!tag) maintain(k);
}

int query(int k, int l, int r) {
pushdown(k);
if (tree[k].l == l && tree[k].r == r) return tree[k].mx;
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= r) {
return query(k << 1, l, r);
} else if (mid < l) {
return query(k << 1 | 1, l, r);
} else {
return max(query(k << 1, l, mid), query(k << 1 | 1, mid + 1, r));
}
}

int ask(int k, int v) {
if (tree[k].l == tree[k].r) return tree[k].col;
int mid = (tree[k].l + tree[k].r) >> 1;
if (mid >= v) return max(tree[k].col, ask(k << 1, v));
else return max(tree[k].col, ask(k << 1 | 1, v));
}

int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) p = top[u], u = fa[top[u]];
else v = fa[top[v]];
}
if (u == v || dep[u] < dep[v]) return u;
else return p = son[v], v;
}

void modify_col(int v, int c) {
col_top[c] = 1, col_bot[c] = v;
for (int pl = 0, pr = 0, tmp; v; ) {
int q = query(1, tid[v], tid[v]), t = ask(1, tid[v]), r = col_top[t];
if (tid[r] < tid[top[v]]) {
modify(1, tid[top[v]], tid[v], c, 1);
modify(1, tid[top[v]], tid[top[v]] + sz[top[v]] - 1, 1 - q, 0);
} else {
modify(1, tid[r], tid[v], c, 1);
modify(1, tid[r], tid[r] + sz[r] - 1, 1 - q, 0);
}
if (pl) modify(1, pl, pr, q - 1, 0);
if (col_bot[t] != v) {
lca(col_bot[t], v);
if (tid[p] != pl) {
modify(1, tid[p], tid[p] + sz[p] - 1, 1, 0), tmp = p;
}
}
if (tid[r] < tid[top[v]]) {
pl = tid[top[v]], pr = tid[top[v]] + sz[top[v]] - 1, v = fa[top[v]];
} else {
pl = tid[r], pr = tid[r] + sz[r] - 1, v = fa[r], col_top[t] = tmp;
}
}
}

int query_col(int u, int v) {
int x = lca(u, v), y = 2 * query(1, tid[x], tid[x]);
return query(1, tid[u], tid[u]) + query(1, tid[v], tid[v]) - y + 1;
}

int main() {
scanf("%d %d", &n, &m), col_cur = n;
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
col_top[i] = col_bot[i] = i;
}
dfs1(1, 0, 1), dfs2(1, 0), build(1, 1, n);
for (int i = 1, op, u, v; i <= m; i++) {
scanf("%d %d", &op, &u);
if (op == 1) {
modify_col(u, ++col_cur);
} else if (op == 2) {
scanf("%d", &v), printf("%d\n", query_col(u, v));
} else {
printf("%d\n", query(1, tid[u], tid[u] + sz[u] - 1));
}
}
return 0;
}