树链剖分，全部MLE了，数组也没有开很大，求助

测试记录

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[101010];
vector<int>G[101010];
int son[101010],siz[101010],dfn[101010],num[101010],fa[101010],de[101010],top[101010],tot=0;
void add(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}
void In(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]); 
	for(int i=1;i<n;i++){
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		add(t1,t2);
	}
}
void dfs(int u,int f){
	siz[u]=1,fa[u]=f,de[u]=de[f]+1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==f)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
void dfs2(int u,int f,int t){
	dfn[u]=++tot,num[tot]=u,top[u]=t;
	if(son[u])dfs2(son[u],u,t);
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==f||v==son[u])continue;
		dfs2(v,u,v);
	}
}
namespace XDS{
	int cnt=1;
	struct as{
		int l,r,son[2];
		long long add,sum;
	}e[404040];
	#define ls(k) e[k].son[0]
	#define rs(k) e[k].son[1]
	void up(int k){
		e[k].sum=e[ls(k)].sum+e[rs(k)].sum;
	}
	void down(int k){
		if(e[k].add){
			e[ls(k)].add+=e[k].add;
			e[ls(k)].sum+=e[k].add*1ll*(e[ls(k)].r-e[ls(k)].l+1);
			e[rs(k)].add+=e[k].add;
			e[rs(k)].sum+=e[k].add*1ll*(e[rs(k)].r-e[rs(k)].l+1);
		}
		e[k].add=0;
	}
	void build(int k,int l,int r){
		e[k].l=l,e[k].r=r;
		if(e[k].l==e[k].r){
			e[k].sum=a[num[l]];
			return;
		}
		ls(k)=++cnt;
		rs(k)=++cnt;
		int mid=e[k].l+e[k].r>>1;
		build(ls(k),l,mid);
		build(rs(k),mid+1,r);
		up(k);
	}
	void add(int k,int l,int r,int v){
		if(e[k].l==l&&e[k].r==r){
			e[k].add+=v;
			e[k].sum+=v*1ll*(e[k].r-e[k].l+1);
			return;
		}
		down(k);
		int mid=e[k].l+e[k].r>>1;
		if(r<=mid){
			add(ls(k),l,r,v);
		}else if(l>mid){
			add(rs(k),l,r,v);
		}else{
			add(ls(k),l,mid,v),add(rs(k),mid+1,r,v);
		}
		up(k);
	}
	long long query(int k,int l,int r){
		if(e[k].l==l&&e[k].r==r){
			return e[k].sum;
		}
		down(k);
		int mid=e[k].l+e[k].r>>1;
		if(r<=mid){
			return query(ls(k),l,r);
		}else if(l>mid){
			return query(rs(k),l,r);
		} else{
			return query(ls(k),l,mid)+query(rs(k),mid+1,r);
		}
	}
	#define build(k,l,r) XDS::build(k,l,r)
	#define add(k,l,r,v) XDS::add(k,l,r,v)
	#define query(k,l,r) XDS::query(k,l,r)
}
long long qsum(int x,int y){
	long long haq=0;
	while(top[x]!=top[y]){
		if(de[top[x]]<de[top[y]])swap(x,y);
		haq+=query(1,num[top[x]],num[x]);
		x=fa[top[x]];
	}
	if(de[x]>de[y])swap(x,y);
	return haq+query(1,num[x],num[y]);
}
void Work(){
	dfs(1,1),dfs2(1,1,1),build(1,1,n);
	while(m--){
		int t1,t2,t3;
		scanf("%d",&t1);
		if(t1==1){
			scanf("%d%d",&t2,&t3);
			add(1,dfn[t2],dfn[t2],t3);
		}else if(t1==2){
			scanf("%d%d",&t2,&t3);
			add(1,dfn[t2],dfn[t2]+siz[t2]-1,t3);
		}else{
			scanf("%d",&t2);
			printf("%lld\n",qsum(1,t2));
		}
	}
}
int main(){
	In();
	Work();
	return 0;
}