题意：
给定一棵树，有点权；两种操作，一是修改某个单点的权值，二是查询某个点为根节点的子树的点权之和。
思路：
dfs序后，子树都处于一个区间里，所以问题就转化成了单点修改、区间求和。
用树状数组维护即可。
代码：
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=1e6+7; int n,m,k; int h[maxn],idx; struct node{ int e,ne; }edge[maxn*2]; ll w[maxn],tr[maxn*4]; void add(int u,int v){///前向星存图 edge[idx]={v,h[u]};h[u]=idx++; } ll in[maxn],out[maxn],timetmp; void dfs(int u,int fa){//dfs记录dfs序列 in[u]=++timetmp; for(int i=h[u];~i;i=edge[i].ne){ int j=edge[i].e; if(j==fa) continue; dfs(j,u); } out[u]=timetmp; } ///树状数组维护区间 ll lowbit(int x){ return x&(-x); } void update(int pos,int val){ while(pos<maxn){ tr[pos]+=val; pos=pos+lowbit(pos); } } ll qask(int pos){ ll res=0; while(pos){ res+=tr[pos]; pos=pos-lowbit(pos); } return res; } int main(){ cin>>n>>m>>k; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<n;i++){ ll u,v; cin>>u>>v; add(u,v);add(v,u); } dfs(k,-1); for(int i=1;i<=n;i++) update(in[i],w[i]); while(m--){ int op;cin>>op; if(op==1){ ll pos,x; cin>>pos>>x; update(in[pos],x); } else{ int pos;cin>>pos; printf("%lld\n",qask(out[pos])-qask(in[pos]-1)); } } return 0; }
