题目思路:
按照正常的并查集思路来想的话,对于操作一 分裂成两颗树后,比较难维护的是其中一颗子树的所有子节点的祖先节点 因为 在find找祖先节点的时候会找到分裂前的的那个祖先节点,如果给每个子节点都更改的话,复杂度不允许
但是,如果我们把删边变为加边的话,这个并查集维护起来就比较方便了 ,我们从这颗树的最终状态向前操作
操作一 删边变为加边
操作二 值的变换,颠倒一下顺序(这里可以用栈记录一个节点的数值变化顺序)
Code:
int n,m,val[maxn],u[maxn],v[maxn],p[maxn],pre[maxn],ans[maxn],res;
int s[maxn],vis[maxn],op[maxn],x[maxn],y[maxn];
stack<int>q[maxn];
int find(int x) {
if(x==p[x]) return x;
return p[x] = find(p[x]);
}
void combine(int x,int y) {
int dx = find(x);
int dy = find(y);
if(dx!=dy) p[dy] = dx,s[dx]+=s[dy];
}
int main() {
n=read(),m=read();
for(int i=1 ; i<=n ; i++) {
int x= read();
p[i]= i;
q[i].push(x);
}
for(int i=1 ; i<=n-1 ; i++) u[i] =read(),v[i] = read();
for(int i=1 ; i<=m ; i++) {
op[i]= read();
if(op[i]==1) x[i] =read(),vis[x[i]] = 1;
else if(op[i]==2) x[i] =read(),y[i] =read(),q[x[i]].push(y[i]);
else if(op[i]==3) x[i] =read();
}
for(int i=1 ; i<=n ; i++) s[i] = val[i] = q[i].top(),q[i].pop();
for(int i=1 ; i<=n-1 ; i++) {
if(vis[i]) continue;
combine(u[i],v[i]);
}
for(int i=m ; i>=1 ; i--) {
if(op[i]==1) {
combine(u[x[i]],v[x[i]]);
} else if(op[i]==2) {
int temp = q[x[i]].top();
q[x[i]].pop();
int t = temp-val[x[i]] ;
s[find(x[i])]+=t;
val[x[i]] = temp;
} else if(op[i]==3) ans[++res] = s[find(x[i])];
}
dep(i,res,1) printf("%d\n",ans[i]);
return 0;
}