splay维护dfs序
我们发现有移动子树这种操作，树剖是做不了了，又要实现子树加，lct又维护不了了，这时我们用splay维护入栈出栈序来支持这些操作。我们记录每个点的入栈时间和出栈时间，这样一个闭合的区间就表示了一个节点的子树，于是我们可以支持更换父亲了。然后是子树加，这里我们把要加的区间提取出来，打标记，但是我们还得维护一个符号总和，因为入栈时间加，出栈时间要减去加的值，因为出栈时间之后得序列就不属于这棵子树了。最后是查询，查询我们只要把查询节点的入栈时间和1号节点提取出来，然后总和就是答案。注意提取区间时不是in[x]-1,out[x]+1,虽然这里节点编号就是对应排名，但是因为这里是出栈入栈序，所以+1-1不一定是序列中下一个节点，所以我们要查询前继后继，也就是提取pre(in[x])和nxt(out[x])
然后还卡时间，我用fread卡过去了
#include<bits/stdc++.h> using namespace std; const int N = 400010, Maxlen = 100 * N; int n, m, dfs_clock = 1, root; int in[N], out[N]; long long w[N]; vector<int> G[N]; char buf[Maxlen], *C = buf; int Len; inline int read() { int x = 0; while (*C < '0' || '9' < *C) ++C; while ('0' <= *C && *C <= '9') x = x * 10 + *C - '0', ++C; return x; } namespace Splay_tree { int cnt; int child[N][2], fa[N], st[N]; long long sum[N], key[N], tag[N], tim[N], sum_tim[N]; inline bool wh(int x) { return child[fa[x]][1] == x; } inline void update(int x) { sum[x] = sum[child[x][0]] + sum[child[x][1]] + key[x]; sum_tim[x] = sum_tim[child[x][0]] + sum_tim[child[x][1]] + tim[x]; } inline void pushdown(int x) { if(tag[x] == 0) return; tag[child[x][0]] += tag[x]; tag[child[x][1]] += tag[x]; key[child[x][0]] += tag[x] * tim[child[x][0]]; key[child[x][1]] += tag[x] * tim[child[x][1]]; sum[child[x][0]] += tag[x] * sum_tim[child[x][0]]; sum[child[x][1]] += tag[x] * sum_tim[child[x][1]]; tag[x] = 0; } inline void rotate(int x) { int y = fa[x], z = fa[y], t = wh(x); fa[x] = z; child[z][wh(y)] = x; child[y][t] = child[x][t ^ 1]; fa[child[x][t ^ 1]] = y; child[x][t ^ 1] = y; fa[y] = x; update(y); update(x); } inline void up(int x) { int top = 0, now = x; while(now != root) { st[++top] = now; now = fa[now]; } st[++top] = root; for(int i = top; i; --i) pushdown(st[i]); } inline void splay(int x, int t) { up(x); for(int f; (f = fa[x]) != t; rotate(x)) if(fa[f] != t) rotate(wh(x) == wh(f) ? f : x); if(!t) root = x; } inline void build(int l, int r, int &x, int last) { if(l > r) return; int mid = (l + r) >> 1; x = mid; fa[x] = last; build(l, mid - 1, child[x][0], x); build(mid + 1, r, child[x][1], x); update(x); } inline int pre(int x) { splay(x, 0); x = child[x][0]; while(child[x][1]) x = child[x][1]; return x; } inline int nxt(int x) { splay(x, 0); x = child[x][1]; while(child[x][0]) x = child[x][0]; return x; } inline void change(int x, int y) { int a = pre(in[x]), b = nxt(out[x]); splay(a, 0); splay(b, root); int t = child[child[root][1]][0]; fa[t] = child[child[root][1]][0] = 0; update(child[root][1]); update(root); a = nxt(in[y]); splay(in[y], 0); splay(a, root); fa[t] = child[root][1]; child[child[root][1]][0] = t; update(child[root][1]); update(root); } inline void ask(int x) { x = nxt(in[x]); splay(1, 0); splay(x, root); int t = child[child[root][1]][0]; printf("%lld ", sum[t]); } inline void add(int x, int delta) { int a = pre(in[x]), b = nxt(out[x]); splay(a, 0); splay(b, root); int t = child[child[root][1]][0]; tag[t] += delta; sum[t] += delta * sum_tim[t]; key[t] += delta * tim[t]; } } using namespace Splay_tree; void dfs(int u) { in[u] = ++dfs_clock; tim[in[u]] = 1; key[in[u]] = w[u]; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; dfs(v); } out[u] = ++dfs_clock; key[out[u]] = -w[u]; tim[out[u]] = -1; } int main() { // freopen("galaxy20.in", "r", stdin); // freopen("output.txt", "w", stdout); Len = fread(C, 1, Maxlen, stdin); buf[Len] = ' '; n = read(); for(int i = 2; i <= n; ++i) { int u = read(); G[u].push_back(i); } for(int i = 1; i <= n; ++i) w[i] = read(); dfs(1); ++dfs_clock; build(1, dfs_clock, root, 0); m = read(); while(m--) { char c; int x, y; for(c = *C; c < 'A' || c > 'Z'; ++C, c = *C); if(c == 'Q') { x = read(); ask(x); } if(c == 'C') { x = read(); y = read(); change(x, y); } if(c == 'F') { x = read(); y = read(); add(x, y); } } // fclose(stdin); // fclose(stdout); return 0; }