求和

感受

思路

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;//1061109567 大约1e9
const ll INF = 0x3f3f3f3f3f3f3f3f;//4557430888798830399 大约4e18 且INF + INF < long long最大值
const int maxn = 1e6 + 10;
ll sum[maxn], a[maxn];
int n, m, k;
struct edge{
    int v, nex;
}e[maxn << 1];
int head[maxn], cnt, dfn, in[maxn], out[maxn];
void init(){
    cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1;
    }
}
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void add(int x, ll val){
    while(x <= n){
        sum[x] += val;
        x += lowbit(x);
    }
}
ll getsum(int x){
    ll ans = 0;
    while(x){
        ans += sum[x];
        x -= lowbit(x);
    }
    return ans;
}
void dfs(int u, int fa){
    int v; in[u] = ++dfn;
    add(in[u], a[u]);
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
    }
    out[u] = dfn;
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    init();
    int u, v, opt;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(k, 0);
    while(m--){
        scanf("%d", &opt);
        if(opt == 1){
            scanf("%d%d", &u, &v);
            add(in[u], v);
        }
        else{
            scanf("%d", &u);
            printf("%lld\n", getsum(out[u]) - getsum(in[u] - 1));
        }
    }
    return 0;
}