题目大意

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。

操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

分析

真就是一见到这类题就得先写一次，发现错，再写一次

想清楚再写行不 -.-

方法1：树剖

方法2：入栈出栈序

入栈+，出栈 -

一个点x到根路径和，就是sum[1,in[x]]

如何区间修改呢

线段树上记录区间中 +的个数减去 -的个数

就是一次修改中权值总体要增加多少个delta

具体见代码

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int M=100007;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

LL val[M];

int n,m;

int g[M],te;

struct edge{

	int y,nxt;

}e[M<<1];

void addedge(int x,int y){

	e[++te].y=y;e[te].nxt=g[x];g[x]=te;

}

int st[M],ed[M],ty[M<<1],dd[M<<1],tdfn=0;

void dfs(int x,int fa){

	st[x]=++tdfn;

	ty[tdfn]=1;

	dd[tdfn]=val[x];

	int p,y;

	for(p=g[x];p;p=e[p].nxt)

	if((y=e[p].y)!=fa) dfs(y,x);

	ed[x]=++tdfn;

	ty[tdfn]=-1;

	dd[tdfn]=-val[x];

}

struct seg{

	LL sum,tag,sz;

}a[M<<3];

void pushup(int x){

	a[x].sum=a[x<<1].sum+a[x<<1|1].sum;

}

void totag(int x,LL d){

	a[x].sum+=d*a[x].sz;

	a[x].tag+=d;

}

void pushdown(int x){

	if(a[x].tag){

		totag(x<<1,a[x].tag);

		totag(x<<1|1,a[x].tag);

		a[x].tag=0;

	}

}

void build(int x,int l,int r){

	if(l==r){

		a[x].sum=dd[l];

		a[x].sz=ty[l];

		a[x].tag=0;

		return;

	}

	int mid=l+r>>1;

	build(x<<1,l,mid);

	build(x<<1|1,mid+1,r);

	pushup(x);

	a[x].sz=a[x<<1].sz+a[x<<1|1].sz;

}

void add(int x,int l,int r,int tl,int tr,LL d){

	if(tl<=l&&r<=tr){

		totag(x,d);

		return;

	}

	int mid=l+r>>1;

	pushdown(x);

	if(tl<=mid) add(x<<1,l,mid,tl,tr,d);

	if(mid<tr) add(x<<1|1,mid+1,r,tl,tr,d);

	pushup(x);

}

LL get(int x,int l,int r,int tl,int tr){

	if(tl<=l&&r<=tr) return a[x].sum;

	int mid=l+r>>1;

	pushdown(x);

	LL res=0;

	if(tl<=mid) res+=get(x<<1,l,mid,tl,tr);

	if(mid<tr) res+=get(x<<1|1,mid+1,r,tl,tr);

	return res;

}

int main(){

	int i,kd,x,y;

	n=rd(); m=rd();

	for(i=1;i<=n;i++) val[i]=rd();

	for(i=1;i<n;i++){

		x=rd(),y=rd();

		addedge(x,y);

		addedge(y,x);

	}

	dfs(1,0);

	build(1,1,2*n);

	while(m--){

		kd=rd();

		if(kd==1){

			x=rd(); y=rd();

			add(1,1,2*n,st[x],st[x],y);

			add(1,1,2*n,ed[x],ed[x],y);

		}

		else if(kd==2){

			x=rd(); y=rd();

			add(1,1,2*n,st[x],ed[x],y);

		}

		else{

			x=rd();

			printf("%lld\n",get(1,1,2*n,1,st[x]));

		}

	}

	return 0;

}