水题笔记_ Codevs 水果姐逛水果街Ⅰ ~ Ⅲ [线段树, LCA, 链剖]

耐心仔细地推式子才可能写出题来

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈嗝~老娘终于A辣

这里写图片描述

懵逼的 题目

传送至 Codevs

扯淡的 题解

用线段树保存 [从 left 到 right 最小的价钱 / 最大的价钱 / 从左到右最大的收益 / 从右到左最大的收益]
(minz / maxz / maxl / maxr)

1
2
3
4
5
6
b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz);
b[dq].minz = min(b[LS(dq)].minz, b[RS(dq)].minz);
b[dq].maxl = max(max(b[LS(dq)].maxl, b[RS(dq)].maxl), // 最大的收益的买和卖的位置在左或右儿子的完整区间中
b[RS(dq)].maxz - b[LS(dq)].minz); // 最大收益的买和卖的位置一个在左儿子的区间内, 一个在右儿子的区间内
b[dq].maxr = max(max(b[LS(dq)].maxr, b[RS(dq)].maxr), // 同上, 但要注意是从右往左走, 注意哪个减哪个
b[LS(dq)].maxz - b[RS(dq)].minz);

然后发现用一个线段树存这么多东西比较麻烦, 那干脆一个存从左往右一个从右往左好了…用空间的浪费换来了一点代码复杂度…

Ⅱ 的话其实没必要用树剖做啊…

写一个简单的LCA, 记录 [从当前节点向上跳 (1 << i) 个节点的 最小价钱 / 最大价钱 / 从上向下走的最大收益 / 从下向上走的最大收益]
(minz[x][i], maxz[x][i], maxd[x][i], maxu[x][i])
建树和上面一样, 需要注意这里记录的是点权, 数组的初始值应该包括当前节点, 查询亦然

Ⅲ 是树剖…无法逃避的树剖…
还专门去学了树剖
存储的值和上面的一样…更新是单点更新也很简单…需要注意push_up的时候maxu / maxd的更新要包括最大收益的买卖节点跨过mid的情况…查询也是…要返回最大值和最小值….
然后你会发现T了3个点…因为如果分别查询最大值和最小值的话常数会大到飞起…以至于refun真 dalao都说”要是能卡过去我直播吃屎”结果真的过了233333
所以要直接返回一个结构体…包含(maxu / maxd) && maxz && minz…于是就200ms-的AC辣~ 好像比题解还快?

沙茶的 代码

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXQ (200000 + 5)
#define INF (0x7ffffff)
#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)

const int root = 1;
using namespace std;

struct node
{
int le;
int ri;
int maxz;// [le, ri]中的最大值
int minz;// [le, ri]中的最小值
int maxl;// 从左往右或者从右往左的最大收益
// int ltr;// [le, ri]中, 从小(左)到大(右)走的最大值
// int rtl;// [le, ri]中, 从大(右)到小(左)走的最大值
}bl[MAXN << 2], br[MAXN << 2];

int n;
int q;
int la[MAXN];
int ra[MAXN];
void js(int*, node*, int, int, int);
int cx(node*, int, int, int);
int cxmax(node*, int, int, int);
int cxmin(node*, int, int, int);
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &la[i]);
ra[n - i + 1] = la[i];
}
js(la, bl, root, 1, n);
js(ra, br, root, 1, n);
scanf("%d", &q);
int srx, sry;
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &srx, &sry);
if (srx > sry)
{
printf("%d\n", cx(br, root, n - srx + 1, n - sry + 1));
}
else
{
printf("%d\n", cx(bl, root, srx, sry));
}
}
return 0;
}
void js(int* a, node* b, int dq, int le, int ri)
{
if (le > ri)
return ;
b[dq].le = le;
b[dq].ri = ri;
if (le == ri)
{
b[dq].maxz = b[dq].minz = a[le];
b[dq].maxl = 0;
}
else
{
int mi = (le + ri) >> 1;
js(a, b, LS(dq), le, mi);
js(a, b, RS(dq), mi + 1, ri);
b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz);
b[dq].minz = min(b[LS(dq)].minz, b[RS(dq)].minz);
b[dq].maxl = max(max(b[LS(dq)].maxl, b[RS(dq)].maxl), b[RS(dq)].maxz - b[LS(dq)].minz);
}
}
int cx(node* b, int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].maxl;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cx(b, RS(dq), le, ri);
}
else if (ri <= mi)
{
return cx(b, LS(dq), le, ri);
}
else
{
int slmax = cx(b, LS(dq), le, mi), srmax = cx(b, RS(dq), mi + 1, ri);
int lmin = cxmin(b, dq, le, mi), rmax = cxmax(b, dq, mi + 1, ri);
return max(max(slmax, srmax), rmax - lmin);
// return max(max(cx(b, LS(dq), le, mi), cx(b, RS(dq), mi + 1, ri)), b[RS(dq)].maxz - b[LS(dq)].minz);
}
}
}
int cxmax(node* b, int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].maxz;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cxmax(b, RS(dq), le, ri);
}
else if (ri <= mi)
{
return cxmax(b, LS(dq), le, ri);
}
else
{
return max(cxmax(b, LS(dq), le, mi), cxmax(b, RS(dq), mi + 1, ri));
}
}
}
int cxmin(node* b, int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].minz;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cxmin(b, RS(dq), le, ri);
}
else if (ri <= mi)
{
return cxmin(b, LS(dq), le, ri);
}
else
{
return min(cxmin(b, LS(dq), le, mi), cxmin(b, RS(dq), mi + 1, ri));
}
}
}

/*
10
2 8 15 1 10 5 19 19 3 5
1
6 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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXQ (10000 + 5)
#define MAXL (20 + 5)
#define INF (0x7ffffff)
#define LL long long
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
//#define DBG emmmmm
const int root = 1;
using namespace std;

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

int n;
int q;
int lgn;

int d[MAXN][MAXL];
int fa[MAXN];
int mon[MAXN];
int minc[MAXN][MAXL];
int maxc[MAXN][MAXL];
int maxd[MAXN][MAXL]; // 从上到下
int maxu[MAXN][MAXL]; // 从下到上
int deep[MAXN];

int lg(int);
void init(int, int);
int lca(int, int);
void adn(int, int);
int main()
{
scanf("%d", &n);
lgn = lg(n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &mon[i]);
}
int srx, sry;
for (int i = 1; i < n; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
d[root][0] = fa[root] = root;
// maxc[root][0] = minc[root][0] = mon[root];
init(root, 1);
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &srx, &sry);
printf("%d\n", max(0, lca(srx, sry)));
}
return 0;
}
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
int lg(int x)
{
int re = 0;
for (; (1 << re) <= x; re++)
;
return re;
}
void init(int dq, int de)
{
deep[dq] = de;
minc[dq][0] = min(mon[dq], mon[fa[dq]]);
maxc[dq][0] = max(mon[dq], mon[fa[dq]]);
maxd[dq][0] = mon[dq] - mon[fa[dq]];
maxu[dq][0] = mon[fa[dq]] - mon[dq];
for (int i = 1; i <= lgn; i++)
{
d[dq][i] = d[d[dq][i - 1]][i - 1];
maxc[dq][i] = max(maxc[dq][i - 1], maxc[d[dq][i - 1]][i - 1]);
minc[dq][i] = min(minc[dq][i - 1], minc[d[dq][i - 1]][i - 1]);
maxd[dq][i] = max(max(maxd[dq][i - 1], maxd[d[dq][i - 1]][i - 1]), maxc[dq][i - 1] - minc[d[dq][i - 1]][i - 1]);
maxu[dq][i] = max(max(maxu[dq][i - 1], maxu[d[dq][i - 1]][i - 1]), maxc[d[dq][i - 1]][i - 1] - minc[dq][i - 1]);
}
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].to != fa[dq])
{
d[b[i].to][0] = fa[b[i].to] = dq;
init(b[i].to, de + 1);
}
}
}
int lca(int x, int y)
{
// int re = 0;
int dqu = 0;
int dqd = 0;
int dqmax = 0;
int dqmin = INF;
int tmin = INF;
int fmax = 0;
if (deep[x] <= deep[y])
{
dqmin = mon[x];
for (int i = lgn; i >= 0; i--)
{
if (deep[x] == deep[y])
break;
if (deep[x] <= deep[d[y][i]])
{
tmin = minc[y][i];
dqd = max(dqd, maxd[y][i]);
dqd = max(dqd, dqmax - tmin);
dqmax = max(dqmax, maxc[y][i]);
y = d[y][i];
}
}
}
else
{
dqmax = mon[y];
for (int i = lgn; i >= 0; i--)
{
if (deep[x] == deep[y])
break;
if (deep[d[x][i]] >= deep[y])
{
fmax = maxc[x][i];
dqu = max(dqu, maxu[x][i]);
dqu = max(dqu, fmax - dqmin);
dqmin = min(dqmin, minc[x][i]);
x = d[x][i];
}
}
}
if (x == y)
{
return max(dqmax - dqmin, max(dqu, dqd));
}
for (int i = lgn; i >= 0; i--)
{
if (d[x][i] != d[y][i])
{
tmin = minc[y][i];
fmax = maxc[x][i];
dqu = max(dqu, maxu[x][i]);
dqd = max(dqd, maxd[y][i]);
dqu = max(dqu, fmax - dqmin);
dqd = max(dqd, dqmax - tmin);
dqmin = min(dqmin, minc[x][i]);
dqmax = max(dqmax, maxc[y][i]);
x = d[x][i], y = d[y][i];
}
}
dqu = max(dqu, maxu[x][0]);
dqd = max(dqd, maxd[y][0]);
dqmax = max(dqmax, maxc[y][0]);
dqmin = min(dqmin, minc[x][0]);
return max(dqmax - dqmin, max(dqd, dqu));
}

/*
10
5 3 2 1 6 5 4 6 0 8
1 9
1 10
10 7
10 3
1 8
7 6
9 2
2 5
5 4
10
7 5
*/

/*
10
2 1 5 2 5 5 3 9 5 8
1 2
2 9
9 4
9 3
4 7
3 8
1 6
7 10
10 5
1
8 10
*/

调到怀疑人生的链剖…

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
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define MAXQ (100000 + 5)
#define INF (0x7ffffff)
#define LL long long
#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;
int g[MAXN];

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

struct node
{
int le;
int ri;
int maxz; // 一条重链内的最大值
int minz; // 一条重链内的最小值
int maxu; // 链内 从下面节点到上面节点的最大值
int maxd; // 链内 从上面节点到下面节点的最大值
} b[MAXN << 2];

int n;
int a[MAXN];
int cnts;

inline void push_up(int); //
void js(int, int, int); //
void xg(int, int, int); //
node cxmaxd(int, int, int); // 查询链内的 最大向下收益
node cxmaxu(int, int, int); // 最大向上收益
int cxmaxz(int, int, int); // 最大价钱
int cxminz(int, int, int); // 最小价钱
inline int solve(int, int);
void init(int, int);
void dfs(int);
inline void adn(int, int); //
inline void read(int&);
int main()
{
// scanf("%d", &n);
read(n);
for (int i = 1; i <= n; i++)
{
// scanf("%d", &ta[i].wei);
read(ta[i].wei);
}
int sre, srx, sry;
for (int i = 1; i < n; i++)
{
// scanf("%d%d", &srx, &sry);
read(srx), read(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 q;
// scanf("%d", &q);
read(q);
for (int i = 1; i <= q; i++)
{
// scanf("%d%d%d", &sre, &srx, &sry);
read(sre), read(srx), read(sry);
if (!sre)
{
xg(1, ta[srx].start, sry);
}
else
{
printf("%d\n", solve(srx, sry));
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
inline 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;
if (le == ri)
{
b[dq].maxz = b[dq].minz = a[le];
b[dq].maxu = b[dq].maxd = 0;
}
else
{
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
push_up(dq);
}
}
int cxmaxz(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].maxz;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cxmaxz(RS(dq), le, ri);
}
else if (ri <= mi)
{
return cxmaxz(LS(dq), le, ri);
}
else
{
return max(cxmaxz(LS(dq), le, mi), cxmaxz(RS(dq), mi + 1, ri));
}
}
}
int cxminz(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].minz;
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
return cxminz(RS(dq), le, ri);
}
else if (ri <= mi)
{
return cxminz(LS(dq), le, ri);
}
else
{
return min(cxminz(LS(dq), le, mi), cxminz(RS(dq), mi + 1, ri));
}
}
}
node cxmaxu(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq];
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
node re;
if (le > mi)
{
re = cxmaxu(RS(dq), le, ri);
}
else if (ri <= mi)
{
re = cxmaxu(LS(dq), le, ri);
}
else
{
node lr = cxmaxu(LS(dq), le, mi);
node rr = cxmaxu(RS(dq), mi + 1, ri);
re.maxu = max(max(lr.maxu, rr.maxu), lr.maxz - rr.minz);
re.maxz = max(lr.maxz, rr.maxz);
re.minz = min(lr.minz, rr.minz);
// cxmaxz(LS(dq), le, mi) - cxminz(RS(dq), mi + 1, ri);
}
return re;
}
}
node cxmaxd(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq];
}
else
{
node re;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
{
re = cxmaxd(RS(dq), le, ri);
}
else if (ri <= mi)
{
re = cxmaxd(LS(dq), le, ri);
}
else
{
node lr = cxmaxd(LS(dq), le, mi);
node rr = cxmaxd(RS(dq), mi + 1, ri);
re.maxd = max(max(lr.maxd, rr.maxd), rr.maxz - lr.minz);
re.maxz = max(lr.maxz, rr.maxz);
re.minz = min(lr.minz, rr.minz);
// return max(max(cxmaxd(LS(dq), le, mi), cxmaxd(RS(dq), mi + 1, ri)), cxmaxz(RS(dq), mi + 1, ri) - cxminz(LS(dq), le, mi));
}
return re;
}
}
void xg(int dq, int wz, int zh)
{
if (b[dq].le == b[dq].ri)
{
if (b[dq].le == wz)
{
b[dq].maxz = b[dq].minz = zh;
}
}
else
{
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz > mi)
{
xg(RS(dq), wz, zh);
}
else if (wz <= mi)
{
xg(LS(dq), wz, zh);
}
push_up(dq);
}
}
inline void push_up(int dq)
{
int mi = (b[dq].le + b[dq].ri) >> 1;
int le = b[dq].le, ri = b[dq].ri;
b[dq].maxz = max(b[LS(dq)].maxz, b[RS(dq)].maxz);
b[dq].minz = min(b[LS(dq)].minz, b[RS(dq)].minz);
b[dq].maxd = max(max(max(b[LS(dq)].maxd, b[RS(dq)].maxd), b[RS(dq)].maxz - b[LS(dq)].minz), b[RS(dq)].maxz - b[LS(dq)].minz);
b[dq].maxu = max(max(max(b[LS(dq)].maxu, b[RS(dq)].maxu), b[LS(dq)].maxz - b[RS(dq)].minz), b[LS(dq)].maxz - b[RS(dq)].minz);
}

/*
struct tnode
{
int wei; ok in main
int deep; ok in init
int fa; ok in init
int top;
int hs; ok in init
int sum; ok in init
int start;
int end;
}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 wei; ok in main
int deep; ok in init
int fa; ok in init
int top;
int hs; ok in init
int sum; ok in init
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 (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;
}

inline int solve(int fr, int to)
{
node zz;
int re = 0;
int dqd = 0;
int dqu = 0;
int fmax = 0;
int tmax = 0;
int fmin = cxminz(1, ta[fr].start, ta[fr].start);
int tmin = cxminz(1, ta[to].start, ta[to].start);
while (ta[fr].top != ta[to].top)
{
if (ta[ta[fr].top].deep > ta[ta[to].top].deep)
{
zz = cxmaxu(1, ta[ta[fr].top].start, ta[fr].start);
dqu = max(dqu, zz.maxu);
fmax = zz.maxz;
dqu = max(dqu, fmax - fmin);
fmin = min(fmin, zz.minz);
fr = ta[ta[fr].top].fa;
}
else
{
zz = cxmaxd(1, ta[ta[to].top].start, ta[to].start);
dqd = max(dqd, zz.maxd);
tmin = zz.minz;
dqd = max(dqd, tmax - tmin);
tmax = max(tmax, zz.maxz);
to = ta[ta[to].top].fa;
}
}
if (ta[fr].deep > ta[to].deep)
{
zz = cxmaxu(1, ta[to].start, ta[fr].start);
dqu = max(dqu, zz.maxu);
fmax = zz.maxz;
dqu = max(dqu, fmax - fmin);
fmin = min(fmin, zz.minz);
}
else
{
zz = cxmaxd(1, ta[fr].start, ta[to].start);
dqd = max(dqd, zz.maxd);
tmin = zz.minz;
dqd = max(dqd, tmax - tmin);
tmax = max(tmax, zz.maxz);
}
re = max(max(dqd, dqu), tmax - fmin);
return re;
}

inline void read(int& re)
{
re = 0;
bool f = false;
char x = 0;
while (x > '9' || x < '0')
{
x = getchar();
if (!(x ^ '-'))
{
f = true;
x = getchar();
}
}
while (x <= '9' && x >= '0')
{
re = (re << 1) + (re << 3) + (x - '0');
x = getchar();
}
re = (f) ? (-re) : (re);
}

/*
4
16 5 1 15
1 2
1 3
2 4
3
1 3 4
0 3 17
1 4 3
*/

By 工作重心转移 弃坑 的 Cansult