WA #2 #7 #8 #9 #10

Record

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+10,M=N<<1;

int head[N],ver[M],nxt[M],tot=0;
void add(int x,int y)
{
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
int n,m;
int poi[N];
int id[N],nwpoi[N],cnt=0;
int dpt[N],size_[N],top[N];
int fa[N],son[N];

ll tree[N<<2],lazy[N<<2];

void dfs1(int x,int f)
{
	dpt[x]=dpt[f]+1;
	fa[x]=f;
	size_[x]=1;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y==f) continue;
		dfs1(y,x);
		size_[x]+=size_[y];
		if(size_[son[x]]<size_[y]) son[x]=y;
	}
}

void dfs2(int x,int t)
{
	id[x]=++cnt;
	nwpoi[cnt]=poi[x];
	top[x]=t;
	if(!son[x]) return ;
	dfs2(son[x],t);
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}

inline void push_up(int node)
{
	tree[node]=tree[node<<1]+tree[node<<1|1];
}

inline void func(int node,int start,int end,int k)
{
	lazy[node]=lazy[node]+k;
	tree[node]=tree[node]+(ll)k*(end-start+1);
}

void push_down(int node,int start,int end)
{
	if(lazy[node]==0) return ;
	int mid=start+end>>1;
	int lnode=node<<1;
	int rnode=node<<1|1;
	func(lnode,start,mid,lazy[node]);
	func(rnode,mid+1,end,lazy[node]);
	lazy[node]=0;
	return ;
}

void build(int node,int start,int end)
{
	lazy[node]=0;
	if(start==end)
	{
		tree[node]=nwpoi[start];
		return ;
	}
	int mid=start+end>>1;
	int lnode=node<<1;
	int rnode=node<<1|1;
	build(lnode,start,mid);
	build(rnode,mid+1,end);
	
	push_up(node);
}

void update(int node,int start,int end,int l,int r,ll val)
{
	if(l<=start&&end<=r)
	{
		tree[node]+=(ll)val*(end-start+1);
		lazy[node]+=val;
		return ;
	}
	push_down(node,start,end);
	int mid=start+end>>1;
	int lnode=node<<1;
	int rnode=node<<1|1;
	if(l<=mid) update(lnode,start,mid,l,r,val);
	if(r>mid) update(rnode,mid+1,end,l,r,val);
	
	push_up(node);
}

ll query(int node,int start,int end,int l,int r)
{
	if(end<l||start>r) return 0;
	if(l<=start&&end<=r) return tree[node];
	
	push_down(node,start,end);
	int mid=start+end>>1;
	int lnode=node<<1;
	int rnode=node<<1|1;
	ll lsum=query(lnode,start,mid,l,r);
	ll rsum=query(rnode,mid+1,end,l,r);
	return lsum+rsum;
	push_up(node);
}

void query_path(int x,int y)
{
	ll res=0;
	while(top[x]!=top[y])
	{
		if(dpt[top[x]]<dpt[top[y]]) swap(x,y);
		res+=query(1,1,n,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(dpt[x]<dpt[y]) swap(x,y);
	res+=query(1,1,n,id[y],id[x]); 
	printf("%lld\n",res);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",poi+i);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs1(1,1);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int k;
		scanf("%d",&k);
		if(k==1)
		{
			int x;
			ll a;
			scanf("%d%lld",&x,&a);
			update(1,1,n,id[x],id[x],a);
		}
		if(k==2)
		{
			int x;
			ll a;
			scanf("%d%lld",&x,&a);
			update(1,1,n,id[x],id[x]+size_[x]-1,a);
		}
		if(k==3)
		{
			int x;
			scanf("%d",&x);
			query_path(x,1);
		}
	}
	return 0;
}