題目傳送門

時間限制 : 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;
}