rt，好像没遇到过MLE

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,size[N],dep[N],fa[N],top[N],id[N],rk[N],son[N],cnt,node[N],tag[N],w[N];
vector<int>v[N];
inline void dfs1(int p,int faa)
{
	dep[p]=dep[faa]+1;
	fa[p]=faa;
	size[p]=1;
	for(int t:v[p])
	{
		if(t==faa)continue;
		dfs1(t,p);
		size[p]+=size[t];
		if(size[t]>size[son[p]])
		 son[p]=t;
	}
	return;
}
inline void dfs2(int p,int faa)
{
	id[p]=++cnt;
	rk[cnt]=p;
	top[p]=faa;
	if(!son[p])return;
	dfs2(son[p],faa);
	for(int t:v[p])
	{
		if(t==faa||t==son[p])continue;
		dfs2(t,t);
	}
	return;
}
inline void pushup(int p)
{
	node[p]=node[p<<1]+node[p<<1|1];
	return;
}
inline void pushdown(int p)
{
	if(tag[p])
	{
		node[p<<1]+=size[id[p<<1]]*tag[p];
		node[p<<1|1]+=size[id[p<<1|1]]*tag[p];
		tag[p<<1]+=tag[p];
		tag[p<<1|1]+=tag[p];
		tag[p]=0;
	}
	return;
}
inline void build(int p,int l,int r)
{
	if(l==r)
	{
		node[p]=w[rk[l]];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pushup(p);
	return;
}
inline void modify_point(int p,int l,int r,int d,int k)
{
	if(l==r)
	{
		node[p]+=k;
		return;
	}
	int mid=l+r>>1;
	if(d<=mid)modify_point(p<<1,l,mid,d,k);
	else modify_point(p<<1|1,mid+1,r,d,k);
	pushup(p); 
	return;
}
inline void modify_range(int p,int l,int r,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		tag[p]+=k;
		node[p]+=size[id[p]]*k;
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	if(L<=mid)modify_range(p<<1,l,mid,L,R,k);
	if(R>mid)modify_range(p<<1|1,mid+1,r,L,R,k);
	pushup(p); 
	return;
}
inline int query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		return node[p];
	}
	pushdown(p);
	int mid=l+r>>1,ans=0;
	if(L<=mid)ans+=query(p<<1,l,mid,L,R);
	if(R>mid)ans+=query(p<<1|1,mid+1,r,L,R);
	return ans;
}
inline int query_sum(int a,int b)
{
	int res=0;
	while(top[a]!=top[b])
	{
		if(dep[a]<dep[b])swap(a,b);
		res+=query(1,1,n,id[top[a]],id[a]);
		a=fa[top[a]];
	}
	if(dep[a]>dep[b])swap(a,b);
	res+=query(1,1,n,id[a],id[b]);
	return res;
}
int main()
{
 //	freopen(".in","r",stdin);
 //	freopen(".out","w",stdout);
 	ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
 	cin>>n>>m;
 	for(int i=1;i<=n;i++)cin>>w[i];
 	for(int i=1;i<=n-1;i++)
 	{
 		int a,b;
 		cin>>a>>b;
 		v[a].push_back(b);
 		v[b].push_back(a);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op,x,a;
		cin>>op>>x;
		if(op==1)
		{
			cin>>a;
			modify_point(1,1,n,id[x],a);
		}
		if(op==2)
		{
			cin>>a;
			modify_range(1,1,n,id[x],id[x]+size[x]-1,a);
		}
		if(op==3)
		{
			cout<<query_sum(x,1)<<endl;
		}
	}
 	return 0;
}