求和

求和

利用dfs序在子树上的连续性，然后通过单点修改，区间查询即可，这点只要用一颗树状数组即可完成。

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

ll tree[N];

int head[N], to[N << 1], nex[N << 1], cnt = 1;

int l[N], r[N], rk[N], value[N], n, m, k, tot;

void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
}

void dfs(int rt, int fa) {
    l[rt] = ++tot, rk[tot] = rt;
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] == fa) continue;
        dfs(to[i], rt);
    }
    r[rt] = tot;
}

int lowbit(int x) {
    return (-x) & x;
}

void update(int x, int value) {
    while(x <= n) {
        tree[x] += value;
        x += lowbit(x);
    }
}

ll query(int x) {
    ll ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &value[i]);
    }
    for(int i = 1; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(k, 0);
    for(int i = 1; i <= n; i++) {
        update(l[i], value[i]);
    }
    for(int i = 1; i <= m; i++) {
        int op;
        scanf("%d", &op);
        if(op == 1) {
            int a, x;
            scanf("%d %d", &a, &x);
            update(l[a], x);
        }
        else {
            int a;
            scanf("%d", &a);
            printf("%lld\n", query(r[a]) - query(l[a] - 1));
        }
    }
    return 0;
}