5190 - 提高：DFS序和欧拉序:树上操作（区域修改1）
题目传送门
时间限制 : 2 秒
内存限制 : 256 MB
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个 操作，分为三种： 操作 1 ：把某个节点 x 的点权增加 a 。 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
输入
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中 第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
输出
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
样例
输入
5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3
输出
6 9 13
提示
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
C++代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,m,clk;
int dfn[N],siz[N],fa[N],dep[N],son[N],top[N],rk[N];
ll a[N],tree[N<<2],lz[N<<2];
vector<int>g[N];
//计算深度、父亲、子树大小、重儿子
void dfs1(int u,int f)
{fa[u]=f;dep[u]=dep[f]+1;siz[u]=1;int maxson=-1;for(int v:g[u]){if(v==f) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>maxson) maxson=siz[v],son[u]=v;}
}
//建立dfs序和top重链顶点
void dfs2(int u,int t)
{top[u]=t;dfn[u]=++clk;rk[clk]=u;if(son[u]) dfs2(son[u],t);for(int v:g[u])if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
void build(int p,int l,int r)
{if(l==r){tree[p]=a[rk[l]];return;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);tree[p]=tree[p<<1]+tree[p<<1|1];
}
void pushdown(int p,int l,int r)
{if(lz[p]){int mid=(l+r)>>1;tree[p<<1]+=(mid-l+1)*lz[p];tree[p<<1|1]+=(r-mid)*lz[p];lz[p<<1]+=lz[p];lz[p<<1|1]+=lz[p];lz[p]=0;}
}
void update(int p,int l,int r,int x,int y,ll v)
{if(x>r||y<l) return;if(x<=l&&r<=y){tree[p]+=(r-l+1)*v;lz[p]+=v;return;}pushdown(p,l,r);int mid=(l+r)>>1;update(p<<1,l,mid,x,y,v);update(p<<1|1,mid+1,r,x,y,v);tree[p]=tree[p<<1]+tree[p<<1|1];
}
ll query(int p,int l,int r,int x,int y)
{if(x>r||y<l) return 0;if(x<=l&&r<=y) return tree[p];pushdown(p,l,r);int mid=(l+r)>>1;return query(p<<1,l,mid,x,y)+query(p<<1|1,mid+1,r,x,y);
}
ll query_path(int x)
{ll res=0;while(x){res+=query(1,1,n,dfn[top[x]],dfn[x]);x=fa[top[x]];}return res;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs1(1,0);dfs2(1,1);build(1,1,n);while(m--){int op,x;ll v;scanf("%d%d",&op,&x);if(op==1){scanf("%lld",&v);update(1,1,n,dfn[x],dfn[x],v);}else if(op==2){scanf("%lld",&v);update(1,1,n,dfn[x],dfn[x]+siz[x]-1,v);}else printf("%lld\n",query_path(x));}return 0;
}