RT，从模板那儿搬过来改的，WA 2,9,10

// Problem: P3178 [HAOI2015]树上操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3178
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define M 100005
#define ll (i*2)
#define rr (i*2+1)
int n,m,r,p=2000000000,U,V,opt,x,y,z,cntp;
int a[M],w[M],d[M],top[M],id[M],fid[M],siz[M],fa[M],son[M];
/*id[i]=j,意为原节点i的id为j,fid则相反*/
vector<int>roadu[M],road[M];
struct node
{
	int s,fl,fr,laz;
}t[M*9];
void push_down(int i)
{
	if(!t[i].laz) return;
	int k=t[i].laz;
	t[ll].s+=(t[ll].fr-t[ll].fl+1)*k;
	t[rr].s+=(t[rr].fr-t[rr].fl+1)*k;
	t[ll].laz+=k;t[rr].laz+=k;
	t[ll].s%=p;t[rr].s%=p;
	t[i].laz=0;
}
void build(int l,int r,int i)
{
	t[i].fl=l;t[i].fr=r;t[i].laz=0;
	if(l==r)
	{
		t[i].s=w[l];
		if(t[i].s>p){t[i].s%=p;}
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,ll);
	build(mid+1,r,rr);
	t[i].s=t[ll].s+t[rr].s;t[i].s%=p;
}
void plused(int l,int r,int x,int y,int i,int k)/*在区间i[x-y]操作,把[l-r]加上k*/
{
	// cout<<x<<' '<<y<<endl;
	if(x>=l&&y<=r)/*l--x--y--r*/
	{
		t[i].laz+=k;
		t[i].s+=(y-x+1)*k;
		return;
	}
	push_down(i);
	int mid=(x+y)/2;
	if(mid>=l)/*[x-mid]是否交[l-r]? */
	{
		plused(l,r,x,mid,ll,k);
	}
	if(mid<r)
	{
		plused(l,r,mid+1,y,rr,k);
	}
	t[i].s=t[ll].s+t[rr].s;t[i].s%=p;
}
int Query(int l,int r,int x,int y,int i)/*在区间i[x-y]操作,求i与[l-r]的交的和*/
{
	int res=0,mid=(x+y)/2;
	if(x>=l&&y<=r)/*l-r包含x-y  l--x--y--t*/
	{
		return t[i].s%p;
	}
	push_down(i);
	if(mid>=l)
	{
		res+=Query(l,r,x,mid,ll);res%=p;
	}
	if(mid<r)
	{
		res+=Query(l,r,mid+1,y,rr);res%=p;
	}
	return res;
}
void dfs1(int x)
{
	if(x==r){d[x]=1;}
	siz[x]=1;
	int sonm=-1;
	for(int i=0;i<road[x].size();i++)
	{
		if(d[road[x][i]]){continue;}
		d[road[x][i]]=d[x]+1;
		dfs1(road[x][i]);
		fa[road[x][i]]=x;
		siz[x]+=siz[road[x][i]];
		if(siz[road[x][i]]>sonm)
		{
			sonm=siz[road[x][i]];
			son[x]=road[x][i];
		}
	}
}
void dfs2(int x,int y)
{
	cntp++;
	w[cntp]=a[x];
	id[x]=cntp;
	fid[cntp]=x;
	top[x]=y;
	if(son[x]==0){return;}
	dfs2(son[x],y);
	for(int i=0;i<road[x].size();i++)
	{
		if(id[road[x][i]]) continue;
		dfs2(road[x][i],road[x][i]);
	}
}
void pLCA()
{
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		// cout<<x<<' '<<top[x]<<' '<<id[x]<<' '<<id[top[x]]<<endl;
		plused(id[top[x]],id[x],1,n,1,z);
		x=fa[top[x]];
	}
	if(d[x]<d[y]) swap(x,y);//d[x]=3,dy=2
	plused(id[y],id[x],1,n,1,z);
}
void qLCA()/*询问 x,y 两个点的最短路径权值和*/
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		res+=Query(id[top[x]],id[x],1,n,1)%p;
		res%=p;
		// cout<<res<<endl;
		x=fa[top[x]];
	}
	if(d[x]<d[y]) swap(x,y);//d[x]=3,dy=2
	res+=Query(id[y],id[x],1,n,1)%p;res%=p;
	cout<<res<<endl;
}
void ptree()
{
	plused(id[x],id[x]+siz[x]-1,1,n,1,z);
}
int main()
{
	cin>>n>>m;
	r=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		cin>>U>>V;
		road[U].push_back(V);
		road[V].push_back(U);
	}
	dfs1(r);
	dfs2(r,r);
	// for(int i=1;i<=n;i++)
	// {
		// cout<<top[i]<<' '<<id[i]<<' '<<son[i]<<endl;
	// }
	build(1,n,1);//建xds
	for(int i=1;i<=m;i++)
	{
		cin>>opt;
		if(opt==1)
		{
			cin>>x>>z;y=x;
			pLCA();
		}
		if(opt==2)
		{
			cin>>x>>z;
			ptree();
		}
		if(opt==3)
		{
			cin>>x;y=1;
			qLCA();
		}
	}
	return 0;
}