学习笔记_ 树链剖分[线段树, 学习笔记, 树链剖分]

树剖可以把树上的信息映射到一条链上

树剖可以解决树上两点之间的快速(10 ^ 5左右)查询和修改问题…
其实树剖并不是一种算法…而更像一种思想…
毕竟剖完了还要用各种数据结构
建议学习之前先看看这个会有助于理解…
开完上面那个你应该知道: 一个节点的子树在DFS序列中是挨在一起的…
两个的思想差不多…都是把树上的值转换到序列上…然后就可以用一些喜闻乐见的数据结构或者DP来做惹…只不过转换的依据不同…一个是直接按照DFS序一个是按照子节点的多少…
树剖中经常用的是一种叫做 [轻重链剖分] 的东西…也就是说根据 [一个节点在他的兄弟中节点的多少] 来转换这颗树…先明确几个概念…

重儿子: siz[u]为v的子节点中siz值最大的, 那么u就是v的重儿子
轻儿子: v的其它子节点
重边: 点v与其重儿子的连边
轻边: 点v与其轻儿子的连边
重链: 由重边连成的路径
轻链: 轻边(一条轻边就是一条轻链)
链顶(top): 一条链(轻或重)中的的深度最小的节点
跳一条链(沿着一条链走): 把一个节点变成这个节点所在链的链顶的父亲

然后就可以把好好的一棵树分成几条轻链和几条重链
上面这些玩意一遍DFS就能求出来惹…对吧?
求这些不是白求的…求出来就有几个性质…

  1. 如果(v,u)为轻边, 则sum[u] * 2 <= sum[v];
  2. 从根到某一点的路径上轻链 or 重链的个数都不大于logn

证明…

  1. 显然如果一个子节点的sumsum[v], 比他父节点的sum值的一半还大的话这个子节点是不是就是重儿子了…?(兄弟节点的sum没有比v大的了)
  2. 也很显然…由 性质1 得…即使是都沿着轻链(一次只走一层)走(从上往下), 一次也可以减少一半的节点数…更别说重链一次就到链顶了呢…

e.g.1(传送至 Luogu)

那么怎么维护呢…因为重链包含的节点个数多…所以重链用一些高级的数据结构维护…轻链一共就俩节点还不是想怎么维护怎么维护 可以直接维护…
因为重链要用数据结构维护…而数据结构一般都是在序列上工作的…所以要让每一条重链上的所有节点 挨在一起, 所以普通的DFS序(一遍DFS)就不能解决问题了…

总结一下…树剖就是用一种标准(轻重), 把树分成几部分分别维护, 包含点多的部分就用数据结构维护, 包含点少的部分就直接暴力改…

所以例题的流程就是…

  1. DFS第一遍, 求出每一个节点的重儿子
  2. DFS第二遍, 遇到一个节点, 先遍历他的重儿子, 以保证重链在序列上是连续的一块
  3. 建树, 在DFS序列上建立一个数据结构
  4. 在数据结构上维护…

具体修改两点间的权重的话就是像倍增LCA一样…只不过LCA是一次往上跳1 << i个节点, 树剖是一次跳过一条链

复杂度…往上跳的话是logn的…然后加上数据结构一般也是logn的话…总的复杂度大概是两个log

然后做的几个题…

NOI2015 软件包管理 在DFS序列上维护一个能全部置0 / 1的线段树即可, 安装的时候就输出 [个点的深度 - 这个点到根上安装了几个包], 删除的时候就把子树置0即可 一遍过辣开心

SDOI2011 染色 维护一个区间上的 颜色块数 and 区间左侧的颜色 and 区间右侧的颜色 即可, 合并两个子区间的时候注意两个区间交界的颜色如果相同块数要 -= 1…注意可能需要卡常…注意细节…不要乱用别名…别名的别名可能会GG…

水果姐逛水果街Ⅲ 比较麻烦…见我的blog

苹果树 其实并不用剖分…因为没有查询两点间的权重所以直接在DFS序列上做就行…

没了
所以树剖的核心代码大概就是两个DFS wwwwwww
改天有空用树状数组写一下可能更快…

链剖就算告一段落了…接下来开坑网络流…

沙茶的 代码

例题1
注意取膜…不取膜卡30非常伤心…
加了一个end方便修改整个子树

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(a, b) {int t = b; b = a; a = t;}
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
#define INF (0x7ffffff)
#define LL long long

int root;
using namespace std;
struct tnode
{
LL wei; // 节点权值
int start; // 节点在 a 中第一次出现的位置
int end; // 节点的子树全部遍历完后的位置
int top; // 链顶
int deep; // 节点深度
int sum; // 子树节点个数
int fa; // 节点的父亲
int hs; // 节点的重儿子
} ta[MAXN];

struct node
{
int le;
int ri;
LL zh;
LL lazy;
} b[MAXN << 2];

struct edg
{
int from;
int to;
int next;
} tb[MAXN << 1];
int cntb = 0;
int g[MAXN];

LL a[MAXN];
int cnts = 0;
int n;
LL mod;
LL cx(int, int, int);
void xg(int, int, int, LL);
void js(int, int, int);
void init(int, int);
void dfs(int);
void adn(int, int);
void solve(int, int, LL);
LL solve(int, int);
inline void push(int);
int main()
{
int q;
scanf("%d%d%d%lld", &n, &q, &root, &mod);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &ta[i].wei);
ta[i].wei %= mod;
}
int srx, sry;
for (int i = 1; i < n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
ta[root].fa = root;
ta[root].top = root;
init(root, 1);
dfs(root);
js(1, 1, n);
int sre, srz;
for (int i = 1; i <= q; i++)
{
scanf("%d", &sre);
if (sre == 4)
{
scanf("%d", &srx);
printf("%lld\n", cx(1, ta[srx].start, ta[srx].end));
}
else
{
scanf("%d%d", &srx, &sry);
if (sre == 1)
{
scanf("%d", &srz);
srz %= mod;
solve(srx, sry, srz);
}
else if (sre & 1)
{
xg(1, ta[srx].start, ta[srx].end, sry);
}
else
{
printf("%lld\n", solve(srx, sry));
}
}
}
return 0;
}
void js(int dq, int le, int ri)
{
b[dq].le = le;
b[dq].ri = ri;
b[dq].lazy = 0;
if (le == ri)
{
b[dq].zh = a[le];
}
else
{
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
b[dq].zh = (b[LS(dq)].zh + b[RS(dq)].zh) % mod;
}
}
void push(int dq)
{
LL& x = b[dq].lazy;
b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
b[LS(dq)].lazy %= mod, b[RS(dq)].lazy %= mod;
b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
b[LS(dq)].zh %= mod;
b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
b[RS(dq)].zh %= mod;
x = 0;
}
void xg(int dq, int le, int ri, LL zh)
{
if (le > ri)
return ;
if(b[dq].lazy && b[dq].le != b[dq].ri)
push(dq);
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].zh += (ri - le + 1) * zh;
b[dq].zh %= mod;
b[dq].lazy += zh;
b[dq].lazy %= mod;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
xg(RS(dq), le, ri, zh);
}
else if (ri <= mi)
{
xg(LS(dq), le, ri, zh);
}
else
{
xg(LS(dq), le, mi, zh);
xg(RS(dq), mi + 1, ri, zh);
}
b[dq].zh = (b[LS(dq)].zh + b[RS(dq)].zh) % mod;
}
}
LL cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].zh;
}
if(b[dq].lazy && b[dq].le != b[dq].ri)
push(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cx(RS(dq), le, ri);
}
else if (ri <= mi)
{
return cx(LS(dq), le, ri);
}
else
{
return (cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri)) % mod;
}
}
void adn(int fr, int to)
{
tb[++cntb].next = g[fr];
tb[cntb].from = fr;
tb[cntb].to = to;
g[fr] = cntb;
}

void init(int dq, int de)
{
ta[dq].deep = de;
ta[dq].sum = 1;
int maxs = 0;
int& hs = ta[dq].hs;
hs = 0;
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
init(tb[i].to, de + 1);
ta[dq].sum += ta[tb[i].to].sum;
if (ta[tb[i].to].sum > maxs)
{
maxs = ta[tb[i].to].sum;
hs = tb[i].to;
}
}
}
}

void dfs(int dq)
{
ta[dq].start = ++cnts;
a[cnts] = ta[dq].wei;
if (ta[dq].hs)
{
ta[ta[dq].hs].top = ta[dq].top;
dfs(ta[dq].hs);
}
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
}
ta[dq].end = cnts;
}

void solve(int x, int y, LL zh)
{
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep > ta[ta[y].top].deep)
{
swap(x, y);
}
xg(1, ta[ta[y].top].start, ta[y].start, zh);
y = ta[ta[y].top].fa;
}
if (ta[x].deep < ta[y].deep)
xg(1, ta[x].start, ta[y].start, zh);
else
xg(1, ta[y].start, ta[x].start, zh);
}

LL solve(int x, int y)
{
LL re = 0;
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep > ta[ta[y].top].deep)
{
swap(x, y);
}
re += cx(1, ta[ta[y].top].start, ta[y].start);
re %= mod;
y = ta[ta[y].top].fa;
}
if (ta[x].deep < ta[y].deep)
re += cx(1, ta[x].start, ta[y].start);
else
re += cx(1, ta[y].start, ta[x].start);
return re % mod;
}

/*
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
*/

软件包管理

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXQ (100000 + 5)
#define MAXE (20 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
using namespace std;
const int root = 1;

struct edg
{
int from;
int to;
int next;
}tb[MAXN << 1];
int cntb = 0;
int g[MAXN];

struct node
{
int le;
int ri;
int zh;
int lazy;
}b[MAXN << 2];

struct tnode
{
int top;
int fa;
int deep;
int start;
int end;
int hs;
int sum;
}ta[MAXN];

int a[MAXN];
int cnts;

int n;
void js(int, int, int); //
void xg(int, int, int, int); //
int cx(int, int, int); //
void init(int, int); //
void dfs(int); //
int solve(int);
void adn(int, int); //
inline void push_down(int);
inline void push_up(int);
int main()
{
scanf("%d", &n);
int srx;
for (int i = 2; i <= n; i++)
{
scanf("%d", &srx);
ta[i].fa = srx + 1;
adn(ta[i].fa, i);
}
ta[root].fa = root;
init(root, 1);
ta[root].top = root;
dfs(root);
js(1, 1, n);
int q;
scanf("%d", &q);
char sre[MAXE];
for (int i = 1; i <= q; i++)
{
scanf("%s%d", sre, &srx);
++srx;
if (sre[0] == 'i')// install
{
printf("%d\n", ta[srx].deep - solve(srx)); // 计算 srx 到根的路径上安装了 x 个包, 用深度 - x, 并把 srx 到根上的点都置为 1
}
else // uninstall
{

printf("%d\n", cx(1, ta[srx].start, ta[srx].end));
xg(1, ta[srx].start, ta[srx].end, 0); // 计算 srx 的子树中包的数量, 并把 srx 的子树全部置成 0
}
}
return 0;
}
void adn(int from, int to)
{
tb[++cntb].next = g[from];
tb[cntb].from = from;
tb[cntb].to = to;
g[from] = cntb;
}
void js(int dq, int le, int ri)
{
b[dq].le = le;
b[dq].ri = ri;
b[dq].lazy = 0;
if (le == ri)
{
b[dq].zh = a[le];
}
else
{
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
push_up(dq);
}
}
void xg(int dq, int le, int ri, int zh)
{
if (le > ri)
return ;
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].lazy = zh + 1;
b[dq].zh = (ri - le + 1) * zh;
return ;
}
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
xg(RS(dq), le, ri, zh);
}
else if (ri <= mi)
{
xg(LS(dq), le, ri, zh);
}
else
{
xg(LS(dq), le, mi, zh);
xg(RS(dq), mi + 1, ri, zh);
}
push_up(dq);
}
int cx(int dq, int le, int ri)
{
if (le > ri)
return 0;
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].zh;
}
if (b[dq].lazy)
{
push_down(dq);
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cx(RS(dq), le, ri);
}
else if (ri <= mi)
{
return cx(LS(dq), le, ri);
}
else
{
return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
}
inline void push_down(int dq)
{
int& x = b[dq].lazy;
int y = x - 1;
b[LS(dq)].lazy = b[RS(dq)].lazy = x;
b[LS(dq)].zh = (b[LS(dq)].ri - b[LS(dq)].le + 1) * y;
b[RS(dq)].zh = (b[RS(dq)].ri - b[RS(dq)].le + 1) * y;
x = 0;
}
inline void push_up(int dq)
{
b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}

/*
struct tnode
{
int top;
int fa;
int deep;
int start;
int end;
int hs;
int sum;
}ta[MAXN];
*/

void init(int dq, int de)
{
ta[dq].deep = de;
ta[dq].sum = 1;
int maxs = 0;
int hs = 0;
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
init(tb[i].to, de + 1);
ta[dq].sum += ta[tb[i].to].sum;
if (ta[tb[i].to].sum > maxs)
{
maxs = ta[tb[i].to].sum;
hs = tb[i].to;
}
}
}
ta[dq].hs = hs;
}

/*
struct tnode
{
int top;
int fa; // ...
int deep; // ...
int start;
int end;
int hs; // ...
int sum; // ...
}ta[MAXN];
*/

void dfs(int dq)
{
ta[dq].start = ++cnts;
if (ta[dq].hs)
{
ta[ta[dq].hs].top = ta[dq].top;
dfs(ta[dq].hs);
}
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].hs && tb[i].to != ta[dq].fa)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
}
ta[dq].end = cnts;
}
int solve(int x)
{
int re = 0;
while (ta[x].top != root)
{
re += cx(1, ta[ta[x].top].start, ta[x].start);
xg(1, ta[ta[x].top].start, ta[x].start, 1);
x = ta[ta[x].top].fa;
}
re += cx(1, ta[root].start, ta[x].start);
xg(1, ta[root].start, ta[x].start, 1);
return re;
}

/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
*/

染色…注意细节…

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define MAXQ (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define LL long long
#define swap(a, b) {int t = b; b = a; a = t;}
#define INF (0x7ffffff)
const int root = 1;
using namespace std;
struct node
{
int le;
int ri;
LL col;
int lec;
int ric;
int lazy;
}b[MAXN << 2];
struct tnode
{
int col;
int hs;
int fa;
int top;
int sum;
int deep;
int start;
int end;
}ta[MAXN];
struct edg
{
int from;
int to;
int next;
}tb[MAXN << 1];
int cntb = 0;
int g[MAXN];

int n;
int cnts = 0;
int a[MAXN];
void js(int, int, int); // done
void xg(int, int, int, int); // done
node cx(int, int, int); // done
inline void push_up(int);
inline void push_down(int);
void init(int, int); // done
void dfs(int); // done
void solve(int, int, int);
LL solve(int, int);
void adn(int, int);
int main()
{
// freopen("in.in", "r", stdin);
// freopen("wa.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
int q;
// scanf("%d%d", &n, &q);
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
// scanf("%d", &ta[i].col);
cin >> ta[i].col;
}
int srx, sry, srz;
for (int i = 1; i < n; i++)
{
// scanf("%d%d", &srx, &sry);
cin >> srx >> sry;
adn(srx, sry);
adn(sry, srx);
}
ta[root].fa = ta[root].top = root;
init(root, 1);
dfs(root);
js(1, 1, n);
char sre;
for (int i = 1; i <= q; i++)
{
cin >> sre >> srx >> sry;
if (sre == 'C')
{
cin >> srz;
solve(srx, sry, srz);
}
else
{
cout << solve(srx, sry) << endl;
}
}
return 0;
}
void adn(int from, int to)
{
tb[++cntb].next = g[from];
tb[cntb].from = from;
tb[cntb].to = to;
g[from] = cntb;
}
void js(int dq, int le, int ri)
{
b[dq].le = le;
b[dq].ri = ri;
b[dq].lazy = 0;
if (le == ri)
{
b[dq].lec = b[dq].ric = a[le];
b[dq].col = 1;
}
else
{
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
push_up(dq);
}
}
node cx(int dq, int le, int ri)
{
if (b[dq].lazy)
{
push_down(dq);
}
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq];
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi)
{
return cx(LS(dq), le, ri);
}
else if (le > mi)
{
return cx(RS(dq), le, ri);
}
else
{
node lez = cx(LS(dq), le, mi), riz = cx(RS(dq), mi + 1, ri);
node re;
re.lec = lez.lec, re.ric = riz.ric;
re.col = riz.col + lez.col - ((riz.lec == lez.ric) ? (1) : 0);
return re;
}
}
}

/*
struct node
{
int le;
int ri;
int col;
int lec;
int ric;
int lazy;
}b[MAXN << 1];
*/

void xg(int dq, int le, int ri, int co)
{
if (b[dq].lazy)
{
push_down(dq);
}
if (b[dq].le == le && b[dq].ri == ri)
{
b[dq].col = 1;
b[dq].lec = b[dq].ric = b[dq].lazy = co;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi)
{
xg(LS(dq), le, ri, co);
}
else if (le > mi)
{
xg(RS(dq), le, ri, co);
}
else
{
xg(LS(dq), le, mi, co);
xg(RS(dq), mi + 1, ri, co);
}
push_up(dq);
}
}



inline void push_up(int dq)
{
b[dq].lec = b[LS(dq)].lec, b[dq].ric = b[RS(dq)].ric;
b[dq].col = b[RS(dq)].col + b[LS(dq)].col - ((b[RS(dq)].lec == b[LS(dq)].ric) ? (1) : 0);
}

/*
struct node
{
int le;
int ri;
int col;
int lec;
int ric;
int lazy;
}b[MAXN << 1];
*/

inline void push_down(int dq)
{
b[RS(dq)].lec = b[RS(dq)].ric = b[LS(dq)].lec = b[LS(dq)].ric = b[RS(dq)].lazy = b[LS(dq)].lazy = b[dq].lazy;
b[RS(dq)].col = b[LS(dq)].col = 1;
b[dq].lazy = 0;
}

/*
struct tnode
{
int col;
int hs;
int fa;
int top;
int sum;
int deep;
int start;
int end;
}ta[MAXN];
*/

void init(int dq, int deep)
{
ta[dq].deep = deep;
ta[dq].sum = 1;
int maxs = 0;
int hs = 0;
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
init(tb[i].to, deep + 1);
ta[dq].sum += ta[tb[i].to].sum;
if (ta[tb[i].to].sum > maxs)
{
maxs = ta[tb[i].to].sum;
hs = tb[i].to;
}
}
}
ta[dq].hs = hs;
}

/*struct tnode
{
int col; // done in main
int hs; // done in init
int fa; // done in init
int top;
int sum; // done in init
int deep; // done in init
int start;
int end;
}ta[MAXN];
*/

void dfs(int dq)
{
a[++cnts] = ta[dq].col;
ta[dq].start = cnts;
if (ta[dq].hs)
{
ta[ta[dq].hs].top = ta[dq].top;
dfs(ta[dq].hs);
}
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
}
ta[dq].end = cnts;
}

void solve(int x, int y, int col)
{
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
{
swap(x, y);
}
xg(1, ta[ta[x].top].start, ta[x].start, col);
x = ta[ta[x].top].fa;
}
if (ta[x].deep < ta[y].deep)
{
swap(x, y);
}
xg(1, ta[y].start, ta[x].start, col);
}
LL solve(int fr, int to)
{
LL re = 0;
node cxf, cxt;
int lfc, ltc;
lfc = ltc = -1;
while (ta[fr].top != ta[to].top)
{
if (ta[ta[fr].top].deep < ta[ta[to].top].deep) // move to
{
cxt = cx(1, ta[ta[to].top].start, ta[to].start);
re += cxt.col;
re -= ((ltc == cxt.ric) ? (1) : (0));
ltc = cxt.lec;
to = ta[ta[to].top].fa;
}
else
{
cxf = cx(1, ta[ta[fr].top].start, ta[fr].start);
re += cxf.col;
re -= ((lfc == cxf.ric) ? (1) : (0));
lfc = cxf.lec;
fr = ta[ta[fr].top].fa;
}
}
if (ta[fr].deep < ta[to].deep)
{
cxt = cx(1, ta[fr].start, ta[to].start);
re += cxt.col;
re -= ((cxt.ric == ltc) ? (1) : (0));
ltc = cxt.lec;
}
else
{
cxf = cx(1, ta[to].start, ta[fr].start);
re += cxf.col;
re -= ((cxf.ric == lfc) ? (1) : (0));
lfc = cxf.lec;
}
re -= ((lfc == ltc) ? (1) : (0));
return re;
}

苹果树

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define LS(a) ((a) << 1)
#define RS(a) (((a) << 1) | 1)
#define INF (0x7ffffff)
const int root = 1;
using namespace std;
struct node
{
int le;
int ri;
int zh;
}b[MAXN << 2];
struct edg
{
int fr;
int to;
int next;
}tb[MAXN << 1];
int cntb = 0;
int g[MAXN];
struct tnode
{
int wei;
int hs;
int sum;
int deep;
int start;
int end;
int fa;
int top;
}ta[MAXN];

int cnts = 0;
int a[MAXN];
int n;
void adn(int, int);
void js(int, int, int);
void xg(int, int);
int cx(int, int, int);
void init(int, int);
void dfs(int);
void solve(int);
inline void push_up(int);
int main()
{
cin >> n;
int srx, sry;
for (int i = 1; i < n; i++)
{
cin >> srx >> sry;
adn(srx, sry);
adn(sry, srx);
}
ta[root].fa = ta[root].top = root;
init(root, 1);
dfs(root);
js(1, 1, n);
int q;
cin >> q;
char sre;
for (int i = 1; i <= q; i++)
{
cin >> sre >> srx;
if (sre == 'C')
{
xg(1, ta[srx].start);
}
else
{
cout << cx(1, ta[srx].start, ta[srx].end) << endl;
}
}
return 0;
}
void adn(int fr, int to)
{
tb[++cntb].next = g[fr];
tb[cntb].fr = fr;
tb[cntb].to = to;
g[fr] = cntb;
}
void js(int dq, int le, int ri)
{
b[dq].le = le;
b[dq].ri = ri;
if (le == ri)
{
b[dq].zh = a[le];
}
else
{
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
push_up(dq);
}
}
void xg(int dq, int wz)
{
if (b[dq].le == b[dq].ri)
{
if (b[dq].le == wz)
{
b[dq].zh = ((b[dq].zh) ? (0) : 1);
}
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
xg(LS(dq), wz);
else if (wz > mi)
xg(RS(dq), wz);
push_up(dq);
}
}
int cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].zh;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
}
inline void push_up(int dq)
{
b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}

/*
struct tnode
{
int wei;
int hs;
int sum;
int deep;
int start;
int end;
}ta[MAXN];
*/

void init(int dq, int de)
{
ta[dq].deep = de;
ta[dq].hs = 0;
ta[dq].sum = ta[dq].wei = 1;
int maxs = 0;
for (int i = g[dq]; i; i = tb[i].next)
{
if (tb[i].to != ta[dq].fa)
{
ta[tb[i].to].fa = dq;
init(tb[i].to, de + 1);
ta[dq].sum += ta[tb[i].to].sum;
if (ta[tb[i].to].sum > maxs)
maxs = ta[tb[i].to].sum, ta[dq].hs = tb[i].to;
}
}
}

/*
struct tnode
{
int wei; // ...done
int hs; // done
int sum; // ...done
int deep; // ...done
int start;
int end;
}ta[MAXN];
*/

void dfs(int dq)
{
ta[dq].start = ++cnts;
a[cnts] = ta[dq].wei;
if (ta[dq].hs)
{
ta[ta[dq].hs].top = ta[dq].top;
dfs(ta[dq].hs);
}
for (int i = g[dq]; i; i = tb[i].next)
{
if (ta[dq].fa != tb[i].to && tb[i].to != ta[dq].hs)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
}
ta[dq].end = cnts;
}

By 码风奇特代码极长的头都快被剖开的 Cansult