鏈接

思路：

? ? ? ? 對于一個子樹來說，子樹的節點就包括在整顆樹的dfs序中子樹根節點出現的前后之間，所以我們先進行一次dfs，用b數組的0表示區間左端點，1表示區間右端點，同時用a數組來標記dfs序中的值。處理完dfs序后，我們就用dfs序列來建樹，若要查詢或修改一個子樹，則區間就是b0到b1，由于在dfs序列中每個數都會出現兩次，所以查詢的結果是正確答案的兩倍，我們只需要最后除以2即可。

?代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
//#define int long long
//const ll P=2281701377;
const ll P=998244353;
const int mod=1e9+7;int n,m,k,a[N],cnt,b[N][2],va[N];
vector<int> v[N];
ll tree[N*4];
void dfs(int x,int f){b[x][0]=++cnt;a[cnt]=x;for(auto y:v[x]){if(y==f) continue;dfs(y,x);} b[x][1]=++cnt;a[cnt]=x;
}
void build(int p,int l,int r){if(l==r){tree[p]=va[a[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 modify(int p,int l,int r,int a,int x){if(l==r&&l==a){tree[p]+=x;return;}int mid=(l+r)>>1;if(a<=mid) modify(p<<1,l,mid,a,x);else modify(p<<1|1,mid+1,r,a,x);tree[p]=tree[p<<1]+tree[p<<1|1];
}
ll query(int p,int l,int r,int x,int y){if(l>=x&&r<=y){return tree[p];}int mid=(l+r)>>1;ll res=0;if(x<=mid) res+=query(p<<1,l,mid,x,y);if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);tree[p]=tree[p<<1]+tree[p<<1|1];return res;
}
void solve(){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>va[i];}for(int i=1;i<n;i++){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}dfs(k,0);build(1,1,cnt);while(m--){int f,a;cin>>f>>a;if(f==1){int x;cin>>x;modify(1,1,cnt,b[a][0],x);modify(1,1,cnt,b[a][1],x);}else{cout<<query(1,1,cnt,b[a][0],b[a][1])/2<<endl;}}}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}}