题解 SP2939 【QTREE5 - Query on a tree V】
Nemlit
2020-06-27 14:11:34
~~为什么全网的LCT都是我看不懂的做法啊awa~~
~~首先这道题是一道经典的动态点分治题目,于是我们考虑使用LCT~~
考虑$LCT$,非常显然的是,树上任意两点的距离可以被表示成$dep[u]+dep[v]-2\times dep[lca]$,由于我们已经确定了$u$(查询点),所以我们只要找到一个白点$v$最小化$dep[v]-2\times dep[lca]$即可
发现我们$access$之后,能作为$LCA$的点一定是在与查询点相同的$Splay$中,于是我们只需要维护出,对于每一个$Splay$上的节点,找到最小的$dep[v]-2\times dep[x]$即可($x$是$Splay$上的节点$v$是$x$虚儿子子树内的点)
需要维护的$dep[v]$是该点虚儿子子树内的最小值,其实就是说我们需要维护子树信息。直接套用维护子树信息的方法即可。
具体的,每次$access$的时候,更新新的子树信息(实$\to$虚,虚$\to$实)。
然后修改的时候,将修改点$Splay$到根,该点不会是任何点的儿子,直接修改即可
查询的时候,将查询点$Splay$到根,直接然后先算出所有虚儿子的答案,再调出$Splay$里面的最小值即可
### $\rm Code:$
感谢队长$\rm XRZ$帮忙调试
```cpp
/* This code is written by Nemlit */
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define rep(i, a, b) for(re int i = (a); i <= (b); ++ i)
#define drep(i, a, b) for(re int i = (b); i >= (a); -- i)
#define Next(i, u) for(re int i = head[u]; i; i = e[i].next)
#define int long long
#define inf 1023456789000000
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define maxn 200005
namespace Graph {
int head[maxn], cnt;
struct edge { int v, next; }e[maxn << 1];
il void add(int u, int v) { e[++ cnt] = (edge){v, head[u]}, head[u] = cnt; }
}
using namespace Graph;
int n, m, val[maxn], v[maxn], fa[maxn], dep[maxn], h[maxn], ch[2][maxn], p[maxn];
struct Heap {
priority_queue<int,vector<int>,greater<int> >a1, a2;
il void push(int x) { a1.push(x); }
il void pop(int x) { a2.push(x); }
il int top() {
while(!a2.empty() && a1.top() == a2.top()) a1.pop(), a2.pop();
return a1.top();
}
}q[maxn];
#define get_fa(x) (ch[1][fa[x]] == x)
#define isroot(x) (ch[1][fa[x]] == x || ch[0][fa[x]] == x)
il void dfs(int u, int fr) {
fa[u] = fr, dep[u] = dep[fr] + 1;
Next(i, u) if(e[i].v != fr) dfs(e[i].v, u);
}
il void pushup(int x) {
val[x] = h[x], p[x] = q[x].top();
val[x] = min(val[x], min(val[ch[0][x]], val[ch[1][x]])), p[x] = min(p[x], min(p[ch[0][x]], p[ch[1][x]]));
}
il void rotate(int x) {
int y = fa[x], z = fa[y], w = get_fa(x), k = get_fa(y);
ch[w][y] = ch[w ^ 1][x], fa[ch[w ^ 1][x]] = y;
if(isroot(y)) ch[k][z] = x;
fa[x] = z, ch[w ^ 1][x] = y, fa[y] = x;
pushup(y), pushup(x);
}
il void Splay(int x) {
while(isroot(x)) {
int y = fa[x];
if(isroot(y)) rotate(get_fa(x) == get_fa(y) ? y : x);
rotate(x);
}
}
il void access(int x) {
for(re int y = 0; x; y = x, x = fa[x]) {
Splay(x);
if(min(q[ch[1][x]].top(), p[ch[1][x]]) < inf / 10) q[x].push(min(q[ch[1][x]].top(), p[ch[1][x]]));
ch[1][x] = y;
if(min(q[ch[1][x]].top(), p[ch[1][x]]) < inf / 10) q[x].pop(min(q[ch[1][x]].top(), p[ch[1][x]]));
h[x] = q[x].top() - 2 * dep[x], pushup(x);
}
}
signed main() {
n = read();
rep(i, 2, n) {
int u = read(), v = read();
add(u, v), add(v, u);
}
dfs(1, 0), m = read();
rep(i, 0, n) q[i].push(inf), p[i] = val[i] = h[i] = inf;
while(m --) {
int opt = read(), x = read();
if(opt == 0) {
if(v[x]) {
access(x), Splay(x);
q[x].pop(q[x].top()), h[x] = q[x].top() - 2 * dep[x];
pushup(x);
}
else {
access(x), Splay(x);
q[x].push(dep[x]), h[x] = -dep[x];
pushup(x);
}
v[x] ^= 1;
}
else access(x), Splay(x), printf("%lld\n", val[x] > inf / 10 ? -1 : dep[x] + val[x]);
}
return 0;
}
```