求和(dfs序+树状数组)

思路：
最朴素的做法：维护一个dp[i]:以i为子树的所有结点和，然后对于每个节点更新，朴素的更新它父亲节点的值，但是，如果树是一个长链这个就超时了。
正解：
先dfs求一个dfs序，这样以i节点的子树都是在一段区间内，所以我们可以维护一下i的子树的数量，那么求以i为根的子树和就是[dfs(i) - 1,dfs(i) + son[i] - 1]区间和，dfs(i):i节点的dfs序。
子树的和用一个区间和就解决了，那么修改节点i的值无非就是单点更新，树状数组维护一下即可。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 10;
vector<int>G[maxn];
int tot,cnt[maxn];
int n,m,root;
int val[maxn],son[maxn],s[maxn];
void dfs(int u,int fu){
    son[u] = 1;
    cnt[u] = ++tot;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs(v,u);
            son[u] += son[v];
        }
    }
}
void update(int x,int v){
    for(; x <= maxn; x += (x & -x)){
        s[x] += v;
    }
}
int query(int x){
    int sum = 0;
    for(; x ; x -= (x & -x)){
        sum += s[x];
    }
    return sum;
}
void solved(){
    scanf("%d%d%d",&n,&m,&root);
    for(int i = 1; i <= n; i++)scanf("%d",&val[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);
    }
    dfs(root,0);
    for(int i = 1; i <= n; i++)update(cnt[i],val[i]);
    while(m--){
        int ins;scanf("%d",&ins);
        if(1 == ins){
            int a,x;scanf("%d%d",&a,&x);
            update(cnt[a],x);
        }else {
            int a;scanf("%d",&a);
            printf("%d\n",query(cnt[a] + son[a] - 1) - query(cnt[a] - 1));
        }
    }
}
int main(){
    solved();
    return 0;
}