这道题有 3 个操作：
1. 换根
2. 求 LCA
3. 子树修改/子树求和.
对于第一个操作，直接换根就行.
对于第二个操作，分这几种情况讨论：$x,y$ 都在以 1 为根，$rt$ 的子树中，$x,y$ 其中 1 个在子树中，$x,y$ 都不在子树中.
对于都在子树中的情况，答案即为 $lca(x,y)$；对于第 2 种情况，答案为 RT；对于第 3 种情况，可以求 a1=lca(x,rt),a2=lca(y,rt),a3=lca(x,y)，然后我们发现 lca 为 3 者深度最大值对应的那个，然后前两种情况也可以被归纳成 a1,a2,a3 中深度最大的那个.
对于第三个操作，还是分 3 种情况讨论：x=RT，RT 在 x 的子树中，RT 不在 x 的子树中.
代码还是非常好写的，一遍过.
code:
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 100009
#define ll long long
#define lson now<<1
#define rson now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int tim,edges,n,RT;
ll sum[N<<2],lazy[N<<2];
int a[N],dep[N],bu[N],len[N<<2];
int hd[N],to[N<<1],nex[N<<1],fa[20][N],st[N],ed[N];
void add(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs(int x,int ff) {
fa[0][x]=ff,dep[x]=dep[ff]+1;
st[x]=++tim,bu[tim]=x;
for(int i=1;i<20;++i) fa[i][x]=fa[i-1][fa[i-1][x]];
for(int i=hd[x];i;i=nex[i]) {
int y=to[i];
if(y==ff) continue;
dfs(y,x);
}
ed[x]=tim;
}
void pushup(int now) {
sum[now]=sum[lson]+sum[rson];
}
void mark(int now,ll v) {
sum[now]+=(ll)len[now]*v;
lazy[now]+=v;
}
void pushdown(int now) {
if(lazy[now]) {
mark(lson,lazy[now]);
mark(rson,lazy[now]);
lazy[now]=0;
}
}
void build(int l,int r,int now) {
len[now]=r-l+1;
if(l==r) {
sum[now]=a[bu[l]];
return;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
pushup(now);
}
void update(int l,int r,int now,int L,int R,ll v) {
if(l>=L&&r<=R) {
mark(now,v);
return;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,lson,L,R,v);
if(R>mid) update(mid+1,r,rson,L,R,v);
pushup(now);
}
ll query(int l,int r,int now,int L,int R) {
if(l>=L&&r<=R) return sum[now];
pushdown(now);
int mid=(l+r)>>1;
ll re=0;
if(L<=mid) re+=query(l,mid,lson,L,R);
if(R>mid) re+=query(mid+1,r,rson,L,R);
return re;
}
int get_up(int x,int kth) {
for(int i=19;i>=0;--i) {
if(dep[x]-dep[fa[i][x]]<=kth) {
kth-=(dep[x]-dep[fa[i][x]]);
x=fa[i][x];
}
}
return x;
}
int LCA(int x,int y) {
if(dep[x]>dep[y]) swap(x,y);
if(dep[x]!=dep[y]) {
for(int i=19;i>=0;--i) {
if(dep[fa[i][y]]>=dep[x]) y=fa[i][y];
}
}
if(x==y) return x;
for(int i=19;i>=0;--i) {
if(fa[i][x]!=fa[i][y]) {
x=fa[i][x];
y=fa[i][y];
}
}
return fa[0][x];
}
int get_lca(int x,int y) {
int a1=LCA(x,y),a2=LCA(x,RT),a3=LCA(y,RT);
if(dep[a1]<dep[a2]) a1=a2;
if(dep[a1]<dep[a3]) a1=a3;
return a1;
}
void modify_subtree(int x,ll v) {
if(x==RT) {
update(1,n,1,1,n,v);
}
else if(st[RT]>=st[x]&&st[RT]<=ed[x]) {
update(1,n,1,1,n,v);
int z=get_up(RT,dep[RT]-dep[x]-1);
update(1,n,1,st[z],ed[z],-v);
}
else {
update(1,n,1,st[x],ed[x],v);
}
}
ll query_subtree(int x) {
if(x==RT) {
return sum[1];
}
else if(st[RT]>=st[x]&&st[RT]<=ed[x]) {
int z=get_up(RT,dep[RT]-dep[x]-1);
return sum[1]-query(1,n,1,st[z],ed[z]);
}
else {
return query(1,n,1,st[x],ed[x]);
}
}
int main() {
// setIO("input");
int x,y,z,m,op;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<n;++i) {
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
RT=1;
dfs(1,0);
build(1,n,1);
for(int i=1;i<=m;++i) {
scanf("%d",&op);
if(op==1) scanf("%d",&RT);
if(op==2) {
scanf("%d%d%d",&x,&y,&z);
int lca=get_lca(x,y);
modify_subtree(lca,z);
}
if(op==3) {
scanf("%d",&x);
printf("%lld
",query_subtree(x));
}
}
return 0;
}