解：splay维护括号序列，就是进子树一次出子树一次。树上每个点直接记录这两个点的编号。
建树的时候按照分配的编号建树。
#include <bits/stdc++.h>
typedef long long LL;
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
static char buf[],*pa(buf),*pb(buf);
template <class T> inline void read(T &x) {
x = ;
register char c(gc);
while((c<''||c>'')&&c!='-')
c=gc;
register int f(c=='-'?c=gc,-:);
while(c>=''&&c<='')
x=x*+c-,c=gc;
x*=f;
return;
} const int N = ;
const LL INF = 0x3f3f3f3f3f3f3f3fll; struct Edge {
int nex, v;
}edge[N]; int tp; int fa[N], op[N], ed[N], s[N][], root, stk[N], top;
LL large[N], val[N], Val[N], tag[N];
int e[N], num = , n, id[N]; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void DFS(int x, int f) {
id[++num] = x;
op[x] = num;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) continue;
DFS(y, x);
}
id[++num] = x;
ed[x] = num;
return;
} inline void pushup(int x) {
large[x] = std::max(large[s[x][]], large[s[x][]]);
large[x] = std::max(large[x], val[x]);
if(!fa[x]) root = x;
return;
} inline void pushdown(int x) {
if(tag[x]) {
if(s[x][]) {
tag[s[x][]] += tag[x];
val[s[x][]] += tag[x];
large[s[x][]] += tag[x];
}
if(s[x][]) {
tag[s[x][]] += tag[x];
val[s[x][]] += tag[x];
large[s[x][]] += tag[x];
}
tag[x] = ;
}
return;
} void out(int x = root) {
pushdown(x);
if(s[x][]) {
out(s[x][]);
}
printf("%d ", id[x]);
if(s[x][]) {
out(s[x][]);
}
return;
} inline void rotate(int x) {
int y = fa[x];
int z = fa[y];
bool f = (s[y][] == x); fa[x] = z;
if(z) {
s[z][s[z][] == y] = x;
}
s[y][f] = s[x][!f];
if(s[x][!f]) {
fa[s[x][!f]] = y;
}
s[x][!f] = y;
fa[y] = x; pushup(y);
return;
} inline void splay(int x, int g = ) {
int y = x;
stk[top = ] = y;
while(fa[y]) {
y = fa[y];
stk[++top] = y;
}
while(top) {
pushdown(stk[top]);
top--;
} y = fa[x];
int z = fa[y];
while(y != g) {
if(z != g) {
(s[z][] == y) ^ (s[y][] == x) ?
rotate(x) : rotate(y);
}
rotate(x);
y = fa[x];
z = fa[y];
}
pushup(x);
return;
} inline int getLP() {
pushdown(root);
int p = s[root][];
while(s[p][]) {
p = s[p][];
pushdown(p);
}
return p;
} inline int getRP() {
pushdown(root);
int p = s[root][];
while(s[p][]) {
p = s[p][];
pushdown(p);
}
return p;
} int build(int l, int r, int f) {
int mid = (l + r) >> ;
//int x = np(f, Val[id[mid]]);
fa[mid] = f;
val[mid] = large[mid] = Val[id[mid]];
if(l < mid) s[mid][] = build(l, mid - , mid);
if(mid < r) s[mid][] = build(mid + , r, mid);
pushup(mid);
return mid;
} inline void Add(int x, LL v) {
splay(op[x]);
int a = getLP();
splay(ed[x]);
int b = getRP();
splay(b);
splay(a, b);
int z = s[a][];
tag[z] += v;
large[z] += v;
val[z] += v;
pushup(a);
pushup(b);
return;
} int main() { int q, rt, x; LL y;
read(n); read(q); read(rt);
for(register int i = ; i <= n; i++) {
read(Val[i]);
}
for(register int i = ; i < n; i++) {
read(x); read(y);
add(x, y); add(y, x);
} DFS(rt, ); /*for(int i = 1; i <= num + 1; i++) {
printf("%d ", id[i]);
}
puts("");*/ Val[] = val[] = -INF;
root = build(, num + , ); //out(), puts(""); for(int i = , f; i <= q; i++) {
read(f); read(x);
if(f == ) { /// out max subtree x
splay(op[x]);
int a = getLP();
splay(ed[x]);
int b = getRP();
splay(b);
splay(a, b);
printf("%lld\n", large[s[a][]]);
}
else if(f == ) { /// subtree x += y
read(y);
Add(x, y);
}
else if(f == ) { /// change fa[x] -> y
read(y);
splay(op[x]);
int a = getLP();
splay(ed[x]);
int b = getRP(); /*printf("%d op = %d ed = %d \n", x, op[x], ed[x]);
printf("a=%d %d b=%d %d \n", a, id[a], b, id[b]);*/ splay(b);
splay(a, b);
int z = s[a][];
s[a][] = fa[z] = ;
pushup(a);
pushup(b);
splay(op[y]);
int t = getRP();
splay(t, op[y]);
s[t][] = z; fa[z] = t;
pushup(t);
pushup(op[y]);
}
//out(), puts("");
} return ;
}
AC代码