题解 SP2939 【QTREE5 - Query on a tree V】

Nemlit

2020-06-27 14:11:34

Solution

~~为什么全网的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; } ```