翻车笔记_ 遥远的国度 [树链剖分, 倍增, 清奇脑回路]

我哪来的自信…

懵逼的 题目

扯淡的 题解

什么时候讲过的来着…

LCT据说没办法搞子树(贼废, 那就树链剖分吧

我们发现换根是唬人的…对于查询的点$x$
$$
\mathrm{return}\,\,\min \begin{cases}
[x.begin, x.end]\,\,\, newroot = an\,\, ancestor\,\, of\,\,x \\
[1, y.begin - 1]\cup[y.end + 1, n]\,\,\,y\,\,is\,\,a\,\,ancestor\,\,of\,\,newroot\cap fa[y] = x\\
[1, n]\,\,\,x=newroot
\end{cases}
$$
那么现在的问题就转化为了怎么找一个节点$newroot$在另一个节点$x$的哪个子树中, 枚举肯定不行…菊花图就卡炸了..

考虑$LCA$的过程, 最后一步找的是$LCA$的两个儿子(也就是在哪一棵子树中), 那么我们用$LCA$的过程, 就可以找到$newroot$在$x$的哪一棵子树中了…

又: 我一直以为…我写的非常高明不用判断最后一个条件来着…然后发现写残了…调了三节课…重构了两遍…

又又: 仔细想一想$deep$小的是靠上的节点不要晕了…

沙茶的 代码

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
/**************************************************************
Problem: 3083
User: Cansult
Language: C++
Result: Accepted
Time:5164 ms
Memory:35596 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define INF (0x7fffffff)
#define MAXL (20 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
const int root = 1;
int dqroot;
using namespace std;
struct tnode
{
int deep, d[MAXL], top, hs, zh, size, begin, end;
}ta[MAXN];
int a[MAXN], cnta, n, lgn;
struct tedg
{
int from, to, next;
}tb[MAXN << 1];
int tg[MAXN], cntb = -1;
struct node
{
int le, ri, zh, lazy;
}b[MAXN << 3];
void push_up(int dq)
{ b[dq].zh = min(b[LS(dq)].zh, b[RS(dq)].zh); }
void push_down(int dq)
{
int& x = b[dq].lazy;
b[LS(dq)].zh = b[RS(dq)].zh = x;
b[LS(dq)].lazy = b[RS(dq)].lazy = x;
x = 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];
return ;
}
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 (b[dq].le == le && b[dq].ri == ri)
{
b[dq].lazy = b[dq].zh = zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (b[dq].lazy)
push_down(dq);
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 (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (b[dq].lazy)
push_down(dq);
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return min(cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri));
}
void init(int dq, int deep)
{
ta[dq].deep = deep;
ta[dq].size = 1;
ta[dq].hs = 0;
for (int i = 1; i <= lgn; i++)
ta[dq].d[i] = ta[ta[dq].d[i - 1]].d[i - 1];
for (int i = tg[dq]; ~i; i = tb[i].next)
if (tb[i].to != ta[dq].d[0])
{
ta[tb[i].to].d[0] = dq;
init(tb[i].to, deep + 1);
ta[dq].size += ta[tb[i].to].size;
if (ta[tb[i].to].size > ta[ta[dq].hs].size)
ta[dq].hs = tb[i].to;
}
}
void dfs(int dq)
{
a[ta[dq].begin = ++cnta] = ta[dq].zh;
if (ta[dq].hs)
ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
for (int i = tg[dq]; ~i; i = tb[i].next)
if (tb[i].to != ta[dq].d[0] && tb[i].to != ta[dq].hs)
{
ta[tb[i].to].top = tb[i].to;
dfs(tb[i].to);
}
ta[dq].end = cnta;
}
void solve(int x, int y, int 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[x].top].begin, ta[x].begin, zh);
x = ta[ta[x].top].d[0];
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
xg(1, ta[x].begin, ta[y].begin, zh);
}
int findson(const int x)
{
int y = dqroot;
for (int i = lgn; i >= 0; i--)
if (ta[ta[y].d[i]].deep > ta[x].deep) // 这玩意是大于...
y = ta[y].d[i];
return (ta[y].d[0] == x ? y : root);
}
int solve(int x)
{
if (x == dqroot) // 本来以为可以不加这个来着...艹
return cx(1, 1, n);
int y = findson(x);
if (ta[y].deep <= ta[x].deep)
return cx(1, ta[x].begin, ta[x].end);
int re = INF;
if (ta[y].begin > 1)
re = min(re, cx(1, 1, ta[y].begin - 1));
if (ta[y].end < n)
re = min(re, cx(1, ta[y].end + 1, n));
return re;
}
void adn(int from, int to)
{
tb[++cntb].next = tg[from];
tb[cntb].from = from;
tb[cntb].to = to;
tg[from] = cntb;
}
int lg(int x)
{
int re = 0;
for (; (1 << re) <= x; re++)
continue;
return re;
}
int main()
{
// cout << "Hello world!" << endl;
memset(tg, -1, sizeof(tg));
int q;
scanf("%d%d", &n, &q);
lgn = lg(n); // ...
for (int i = 1; i < n; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
for (int i = 1; i <= n; i++) scanf("%d", &ta[i].zh);
ta[root].d[0] = root, ta[root].top = root;
init(root, 1);
dfs(root);
js(1, 1, n);
scanf("%d", &dqroot);
for (int i = 1; i <= q; i++)
{
int sre, srx, sry, srz;
scanf("%d", &sre);
if (sre == 1)
scanf("%d", &dqroot);
else if (sre == 2)
scanf("%d%d%d", &srx, &sry, &srz), solve(srx, sry, srz);
else
scanf("%d", &srx), printf("%d\n", solve(srx));
}
return 0;
}

/*
3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
*/

By sb Cansult