WA on 4 求助

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#include<unordered_map>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}

template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MOD(1e9+7);
template<typename T>
inline T add(T x){return x;}
template<typename T,typename... types>
inline T add(T x,types... y){T z=add<T>(y...);return x+z>=MOD?x+z-MOD:x+z;}
template<typename T>
inline T mul(T x){return x;}
template<typename T,typename... types>
inline T mul(T x,types... y){return (ll)x*mul<T>(y...)%MOD;}
inline int sub(int x,int y){return add(x-y,MOD);}

const int MAXN(1e5+10);

int n,m,a[MAXN];
vector<int>G[MAXN];
int root(1);

int dfn[MAXN],rk[MAXN],tot;
int siz[MAXN],par[MAXN][23],son[MAXN],top[MAXN],dep[MAXN];

inline void dfs1(int u,int fa)
{
	par[u][0]=fa,dep[u]=dep[fa]+1,siz[u]=1;
	rep(i,1,20) par[u][i]=par[par[u][i-1]][i-1];
	for(auto v:G[u]) if(v!=fa)
	{
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
	return;
}

inline void dfs2(int u,int topf)
{
	top[u]=topf;
	dfn[u]=++tot;
	rk[tot]=u;
	if(son[u]) dfs2(son[u],topf);
	for(auto v:G[u]) if(v!=par[u][0]&&v!=son[u]) dfs2(v,v);
	return;
}

struct Segment_Tree
{
	ll tree[MAXN<<2],tag[MAXN<<2];
	inline int lc(int p){return p<<1;}
	inline int rc(int p){return p<<1|1;}
	
	inline void push_up(int u)
	{
		tree[u]=tree[lc(u)]+tree[rc(u)];
		return;
	}
	
	inline void build(int u,int l,int r)
	{
		if(l==r)
		{
			tree[u]=a[rk[l]];
			return;
		}
		int mid=(l+r)>>1;
		build(lc(u),l,mid),build(rc(u),mid+1,r);
		push_up(u);
		return;
	}
	
	inline void lazy_tag(int u,int l,int r,int k)
	{
		tree[u]+=1ll*(r-l+1)*k;
		tag[u]+=k;
		return;
	}
	
	inline void push_down(int u,int l,int r)
	{
		int mid=(l+r)>>1;
		lazy_tag(lc(u),l,mid,tag[u]);
		lazy_tag(rc(u),mid+1,r,tag[u]);
		tag[u]=0;
	}
	
	inline void update(int u,int l,int r,int ln,int rn,int k)
	{
		if(ln>rn) return;
		if(ln<=l&&r<=rn)
		{
			lazy_tag(u,l,r,k);
			return;
		}
		push_down(u,l,r);
		int mid=(l+r)>>1;
		if(ln<=mid) update(lc(u),l,mid,ln,rn,k);
		if(rn>mid) update(rc(u),mid+1,r,ln,rn,k);
		push_up(u);
		return;
	}
	
	inline ll query(int u,int l,int r,int ln,int rn)
	{
		if(ln<=l&&r<=rn) return tree[u];
		push_down(u,l,r);
		int mid=(l+r)>>1;
		ll res=0;
		if(ln<=mid) res+=query(lc(u),l,mid,ln,rn);
		if(rn>mid) res+=query(rc(u),mid+1,r,ln,rn);
		return res;
	}
};
Segment_Tree seg;

inline int LCA(int x,int y)
{
	if(dep[x]<dep[y]) Swap(x,y);
	rev(k,20,0) if(dep[par[x][k]]>=dep[y]) x=par[x][k];
	if(x==y) return x;
	rev(k,20,0) if(par[x][k]!=par[y][k]) x=par[x][k],y=par[y][k];
	return par[x][0];
}

inline bool in(int x)
{
	if(dfn[root]<=dfn[x]&&dfn[x]<=dfn[root]+siz[root]-1) return true;
	return false;
}

inline void update(int x,int k)
{
	if(x==root) seg.update(1,1,n,1,n,k);
	else if(dfn[x]<=dfn[root]&&dfn[root]<=dfn[x]+siz[x]-1)
	{
		int y=root;
		rev(k,20,0) if(dep[par[y][k]]-1>=dep[x]) y=par[y][k];
		int l=dfn[y],r=dfn[y]+siz[y]-1;
		seg.update(1,1,n,1,l-1,k),seg.update(1,1,n,r+1,n,k);
	}
	else seg.update(1,1,n,dfn[x],dfn[x]+siz[x]-1,k);
	return;
}

inline int find(int x,int y)
{
	if(in(x)&&in(y)) return LCA(x,y);
	if(in(x)||in(y)) return root;
	int p=LCA(x,root),q=LCA(y,root);
	if(dep[p]>=dep[q]) return p;
	return q;
}

inline ll query(int x)
{
	if(x==root) return seg.query(1,1,n,1,n);
	if(dfn[x]<=dfn[root]&&dfn[root]<=dfn[x]+siz[x]-1)
	{
		int y=root;
		rev(k,20,0) if(dep[par[y][k]]-1>=dep[x]) y=par[y][k];
		return seg.query(1,1,n,1,n)-seg.query(1,1,n,dfn[y],dfn[y]+siz[y]-1);
	}
	return seg.query(1,1,n,dfn[x],dfn[x]+siz[x]-1);
}

int main()
{
	n=read(),m=read();
	rep(i,1,n) a[i]=read();
	rep(i,2,n)
	{
		int u=read(),v=read();
		G[u].push_back(v),G[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	seg.build(1,1,n);
	while(m--)
	{
		int opt=read(),u=read();
		if(opt==1) root=u;
		else if(opt==2)
		{
			int v=read(),x=read();
			int lca=find(u,v);
			update(lca,x);
		}
		else printf("%lld\n",query(u));
	}
	return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/