树剖 141 行，没过样例。

我知道很不道德但是我还是要求助一下因为我尽力了。

#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
typedef long long ll;
const int N=1e5+5;
int h[N],ne[N<<1],to[N<<1],idx;
int son[N],siz[N],top[N],dfn[N],dep[N],fa[N],cnt;
struct tree{
	int l,r;
	ll sum,lazy;
}tr[N<<2];
int n,q;
void add(int a,int b){
	to[++idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
}
void dfs1(int x){
	son[x]=-1;
	siz[x]=1;
	for(int i=h[x];i!=-1;i=ne[i]){
		int j=to[i];
		if(j==fa[x]) continue;
		fa[j]=x;
		dep[j]=dep[x]+1;
		dfs1(j);
		siz[x]+=siz[j];
		if(son[x]==-1||siz[son[x]]<siz[j]) son[x]=j;
	}
}
void dfs2(int x,int tp){
	top[x]=tp;
	dfn[x]=++cnt;
	if(son[x]==-1) return ;
	dfs2(son[x],tp);
	for(int i=h[x];i!=-1;i=ne[i]){
		int j=to[i];
		if(j!=fa[x]&&j!=son[x]) dfs2(j,j);
	}
}
void pushdown(int id){
	if(tr[id].l!=tr[id].r){
		tr[lid].sum+=(tr[lid].r-tr[lid].l+1)*tr[id].lazy;
		tr[rid].sum+=(tr[rid].r-tr[rid].l+1)*tr[id].lazy;
		tr[lid].lazy+=tr[id].lazy;
		tr[rid].lazy+=tr[id].lazy;
		tr[id].lazy=0;
	}
}
void build(int id,int l,int r){
	tr[id].l=l,tr[id].r=r;
	tr[id].sum=0;
	tr[id].lazy=0;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
}
void modify(int id,int x,int v){
	pushdown(id);
	if(tr[id].l==x&&tr[id].r==x){
		tr[id].sum+=v;
		return ;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(x<=mid) modify(lid,x,v);
	else modify(rid,x,v);
	tr[id].sum=tr[lid].sum+tr[rid].sum;
}
void modify2(int id,int l,int r,int v){
	pushdown(id);
	if(tr[id].l==l&&tr[id].r==r){
		tr[id].sum+=(r-l+1)*v;
		tr[id].lazy+=v;
		return ;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid) modify2(lid,l,r,v);
	else if(l>mid) modify2(rid,l,r,v);
	else{
		modify2(lid,l,mid,v);
		modify2(rid,mid+1,r,v);
	}
	tr[id].sum=tr[lid].sum+tr[rid].sum;
}
ll querytree(int id,int l,int r){
	pushdown(id);
	if(tr[id].l==l&&tr[id].r==r) return tr[id].sum;
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid) return querytree(lid,l,r);
	else if(l>mid) return querytree(rid,l,r);
	else return querytree(lid,l,mid)+querytree(rid,mid+1,r);
}
ll query(int x,int y){
	ll ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=querytree(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dfn[x]<dfn[y]) ans+=querytree(1,dfn[x],dfn[y]);
	else ans+=querytree(1,dfn[y],dfn[x]);
	return ans;
}
int main(){
	memset(h,-1,sizeof h);
	scanf("%d%d",&n,&q);
	build(1,1,n);
	for(int i=1;i<=n;i++){
		int v;
		scanf("%d",&v);
		modify(1,i,v); 
	}
	for(int i=1;i<=n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	while(q--){
		int op,x,a;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d",&x,&a);
			modify(1,dfn[x],a);
		}
		else if(op==2){
			scanf("%d%d",&x,&a);
			modify2(1,dfn[x],dfn[x]+siz[x]-1,a);
		} 
		else{
			scanf("%d",&x);
			printf("%lld\n",query(1,x));
		}
	}
	return 0;
}

有可能有傻逼错误。