题目链接：https://loj.ac/problem/144
题面：
给一棵有根树，这棵树由编号为1…N的N个结点组成。根结点的编号为R。每个结点都有一个权值，结点i的权值为vi?。接下来有M组操作，操作分为两类：
1 a x，表示将结点a的权值增加x；2 a，表示求结点a的子树上所有结点的权值之和。
输入格式：
- 第一行有三个整数 N,M和R。
- 第二行有 N 个整数，第 i 个整数表示 vi?。
- 在接下来的 N?1 行中，每行两个整数，表示一条边。
- 在接下来的 M 行中，每行一组操作。
输出格式：
对于每组 2 a 操作，输出一个整数，表示「以结点 a 为根的子树」上所有结点的权值之和。
数据范围与提示：
解析：在求出此树的dfs序之后，子树是一段连续的区间，可以将对子树的区间操作直接化为对应序列的区间操作。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;int n,m,root,a[MAXN];struct Edge{int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
void addEdge(int u,int v)
{tot++;edge[tot].to=v;edge[tot].next=head[u];head[u]=tot;
}ll bit[MAXN];
inline int lowbit(int x){return x&(-x);}
void add(int i,int v)
{while(i<=n){bit[i]+=v;i+=lowbit(i);}
}
ll sum(int i)
{ll res=0;while(i>0){res+=bit[i];i-=lowbit(i);}return res;
}int Index,l[MAXN],r[MAXN];
//l[u]和r[u]分别是以u为根节点的子树对应的区间左右端点
void dfs(int u,int fa)
{l[u]=++Index;add(Index,a[u]);for(int i=head[u];i;i=edge[i].next){int to=edge[i].to;if(to==fa) continue;dfs(to,u);}r[u]=Index;
}int inline read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int main()
{int u,v,op,pos,val;n=read();m=read();root=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<n;i++){u=read();v=read();addEdge(u,v);addEdge(v,u);}dfs(root,0);for(int i=1;i<=m;i++){op=read();if(op==1){pos=read();val=read();add(l[pos],val);}else{pos=read();printf("%lld\n",sum(r[pos])-sum(l[pos]-1));}}return 0;
}