[HAOI2015]树上操作-树链剖分

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+5;

#define mid ((l+r)>>1)

#define left_son root<<1,l,mid

#define right_son root<<1|1,mid+1,r

#define ll long long

int n,m;

int e,begin[maxn],next[maxn],to[maxn],w[maxn];

struct segment_tree{

	ll sum,mark,l,r;

}tree[maxn<<2];

int son[maxn],id[maxn],father[maxn],cnt,deep[maxn],size[maxn],top[maxn],_map[maxn];

inline void add(int x,int y){

	to[++e] = y;

	next[e] = begin[x];

	begin[x] = e;

}

inline void pushup(int root){

	tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;

}

inline void pushdown(int root){

	if(tree[root].mark){

		tree[root<<1].mark += tree[root].mark;

		tree[root<<1|1].mark += tree[root].mark;

		tree[root<<1].sum += tree[root].mark*(tree[root<<1].r-tree[root<<1].l+1);

		tree[root<<1|1].sum += tree[root].mark*(tree[root<<1|1].r-tree[root<<1|1].l+1);

		tree[root].mark = 0;

	}

}

inline void build(int root,int l,int r){

	tree[root].l = l;

	tree[root].r = r;

	tree[root].mark = 0;

	if(l == r){

		tree[root].sum = w[_map[l]];

		return;

	}

	build(left_son);

	build(right_son);

	pushup(root);

}

inline void update(int root,int l,int r,int al,int ar,ll k){

	if(al > r || ar < l)return;

	if(al <= l && ar >= r){

		tree[root].mark += k;

		tree[root].sum += k*(r-l+1);

		return;

	}

	pushdown(root);

	update(left_son,al,ar,k);

	update(right_son,al,ar,k);

	pushup(root);

}

inline ll query(int root,int l,int r,int al,int ar){

	if(al > r || ar < l)return 0;

	if(al <= l && ar >= r)return tree[root].sum;

	pushdown(root);

	return query(left_son,al,ar)+query(right_son,al,ar);

}

inline ll query_range(int x,int y){

	ll ans = 0;

	while(top[x] != top[y]){

		if(deep[top[x]] < deep[top[y]])swap(x,y);

		ans += query(1,1,cnt,id[top[x]],id[x]);

		x = father[top[x]];

	}

	if(deep[x] > deep[y])swap(x,y);

	ans += query(1,1,cnt,id[x],id[y]);

	return ans;

}

inline void dfs1(int x,int fa,int dep){

	deep[x] = dep;

	father[x] = fa;

	size[x] = 1;

	int maxson = -1;

	for(int i = begin[x];i;i = next[i]){

		int y = to[i];

		if(y == fa)continue;

		dfs1(y,x,dep+1);

		size[x] += size[y];

		if(size[y] > maxson)son[x] = y,maxson = size[y];

	}

}

inline void dfs2(int x,int ntop){

	id[x] = ++cnt;

	top[x] = ntop;

	_map[id[x]] = x;

	if(!son[x])return;

	dfs2(son[x],ntop);

	for(int i = begin[x];i;i = next[i]){

		int y = to[i];

		if(y == father[x] || y == son[x])continue;

		dfs2(y,y);

	}

}

int main(){

	cin>>n>>m;

	for(int i = 1;i <= n;i++)scanf("%d",&w[i]);

	for(int i = 1,u,v;i < n;i++){

		scanf("%d%d",&u,&v);

		add(u,v);

		add(v,u);

	}

	dfs1(1,0,1);

	dfs2(1,1);

	build(1,1,cnt);

	while(m--){

		ll x,y,dispose;

		scanf("%lld%lld",&dispose,&x);

		if(dispose == 1){

			scanf("%lld",&y);

			update(1,1,cnt,id[x],id[x],y);

		}

		if(dispose == 2){

			scanf("%lld",&y);

			update(1,1,cnt,id[x],id[x]+size[x]-1,y);

		}

		if(dispose == 3)printf("%lld\n",query_range(1,x));

	}

	return 0;

}