对于这样的一道题目
给定一棵大小为 n 的有根点权树,要求支持以下操作: 换根 | 单点修改 | 查询子树最小值
我参考的是网上 LCT + set 维护虚子树的做法,我有几点疑惑:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
const int N = 1e5 + 5, inf = 2e9;
int n, q;
int son[N][2], fa[N];
int val[N];
int chain[N], sub[N];
int mn[N];
int rev[N];
int root;
multiset<int> vtree[N];
bool isroot(int x) {return !(son[fa[x]][0] == x || son[fa[x]][1] == x);}
void pushup(int x) {
chain[x] = mn[x] = val[x], sub[x] = inf;
chain[x] = min({chain[x], chain[son[x][0]], chain[son[x][1]]});
sub[x] = min({sub[son[x][0]], sub[son[x][1]], *vtree[x].begin()});
mn[x] = min(chain[x], sub[x]);
}
void pushrev(int x) {swap(son[x][0], son[x][1]), rev[x] ^= 1;}
void pushdown(int x) {
if (!rev[x]) return;
if (son[x][0]) pushrev(son[x][0]);
if (son[x][1]) pushrev(son[x][1]);
rev[x] ^= 1;
}
void pushall(int x) {
if (!isroot(x)) pushall(fa[x]);
pushdown(x);
}
void rotate(int x) {
int y = fa[x], z = fa[y];
int k = son[y][1] == x;
if (!isroot(y)) son[z][son[z][1] == y] = x;
fa[x] = z;
son[y][k] = son[x][k ^ 1], fa[son[x][k ^ 1]] = y;
son[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x) {
pushall(x);
while (!isroot(x)) {
int y = fa[x], z = fa[y];
if (!isroot(y)) rotate(son[z][1] == y ^ son[y][1] == x ? x : y);
rotate(x);
}
}
void access(int x) {
for (int y = 0; x; x = fa[y = x]) {
splay(x);
if (y) vtree[x].erase(vtree[x].lower_bound(mn[y]));
if (son[x][1]) vtree[x].insert(mn[son[x][1]]);
son[x][1] = y, pushup(x);
}
}
void makeroot(int x) {
access(x);
splay(x);
pushrev(x);
}
void link(int x, int y) {
makeroot(x);
fa[x] = y;
vtree[y].insert(mn[x]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
mn[0] = chain[0] = sub[0] = val[0] = inf;
for (int i = 0; i <= n; i++) vtree[i].insert(inf);
for (int i = 1; i <= n; i++) {
int f;
cin >> f >> val[i];
if (!f) root = i;
else link(f, i);
}
makeroot(root);
while (q--) {
char op;
int x, y;
cin >> op >> x;
if (op == 'V') cin >> y, access(x), splay(x), val[x] = y;
if (op == 'E') makeroot(root = x);
if (op == 'Q') access(x), splay(x), cout << min(val[x], *vtree[x].begin()) << "\n";
}
return 0;
}
access(x) + splay(x) 后就能得到 x 的子树了。