rt，题目，树剖卡了很久还是只有80pts

#include<bits/stdc++.h>
#pragma GCC optimeze(2)
#pragma GCC optimeze(3) 
using namespace std;
const int N=1e6+5; 
int read(){	
	int x=0,flag=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*flag;
}
int n,q,ver[N*2],ne[N*2],head[N],root,dfn[N],rk[N],top[N],fa[N],dep[N],tot=0,son[N],size[N],fhz=0,v[N];
long long c[N],d[N],sum1[N],sum2[N];
inline void add(int x,int y){
	ver[++tot]=y,ne[tot]=head[x],head[x]=tot;
}
inline void dfs1(int t,int f,int d){
	dep[t]=d;
	fa[t]=f;
	size[t]=1;
	for(int i=head[t];i;i=ne[i]){
		int to=ver[i];
		if(to==f)continue;
		dfs1(to,t,d+1);
		size[t]+=size[to];
		if(size[to]>=size[son[t]])son[t]=to;
	}
}
inline void dfs2(int t,int op){
	dfn[t]=++fhz;
	rk[fhz]=t;
	top[t]=op;
	if(son[t])dfs2(son[t],op);
	for(int i=head[t];i;i=ne[i]){
		int to=ver[i];
		if(to==son[t]||to==fa[t])continue;
		dfs2(to,to);
	}
}
#define lowbit(x) (x&(-x))
inline void change(int x,long long y){
	long long yy=y*x;
	for(;x<=n;x+=lowbit(x))c[x]+=y,d[x]+=yy;
}
inline long long qu(int x){
	long long  ans=0,k=x,ans2=0;
	while(x){
		ans+=c[x];
		ans2+=d[x];
		x-=lowbit(x);
	}
	ans*=(k+1),x=k;
	return ans-ans2;
}
#define query(l,r) qu(r)-qu(l-1)
#define changee(l,r,x) change(l,x),change(r+1,-x)
signed main(){
	n=read(),q=read(),root=read();
	for(int i=1;i<=n;i++)v[i]=read();
	for(int i=1;i<n;i++){
		int u,v;
		u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	dfs1(root,0,1);
	dfs2(root,root);
	for(long long i=1;i<=n;i++){
		sum1[i]=sum1[i-1]+v[rk[i]]-v[rk[i-1]];
		sum2[i]=sum2[i-1]+(v[rk[i]]-v[rk[i-1]])*i;
		c[i]=sum1[i]-sum1[i-lowbit(i)];
		d[i]=sum2[i]-sum2[i-lowbit(i)];
	}
	while(q--){
		int op,a,b;
		op=read();
		a=read();
		if(op==1){
			int x;
			x=read();
			changee(dfn[a],dfn[a],x);
		}
		if(op==2){
			int x;
			x=read();
			changee(dfn[a],dfn[a]+size[a]-1,x);
		}
		if(op==3){
			b=read();
			int x=a,y=b;
			int fx=top[x],fy=top[y];
			long long ans=0;
			while(fx!=fy){
				if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
				ans+=query(dfn[fx],dfn[x]);
				x=fa[fx],fx=top[x];
			}
			if(dep[x]<dep[y])swap(x,y);
			ans+=query(dfn[y],dfn[x]);	
			printf("%lld\n",ans);
		}
	}
	return 0;
}