Propagating tree

感受

思路

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls o << 1
#define rs o << 1 | 1
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 = 2e5 + 10;
ll lazy[2][maxn << 2];
ll val[2][maxn << 2];
int n, m;
int in[maxn], out[maxn], dfn;
ll a[maxn], f[maxn];
int head[maxn], cnt, dep[maxn];
struct edge{
    int v, nex;
}e[maxn << 1];
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 dfs(int u, int fa, int d){
    dep[u] = d; in[u] = ++dfn;
    f[in[u]] = a[u];
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == fa) continue;
        dfs(v, u, d ^ 1);
    }
    out[u] = dfn;
}
void build(int o, int l, int r){
    if(l == r){
        val[0][o] = val[1][o] = f[l];
        return ;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}
void push(int o, int opt){
    if(lazy[opt][o]){
        val[opt][ls] += lazy[opt][o];
        val[opt][rs] += lazy[opt][o];
        lazy[opt][ls] += lazy[opt][o];
        lazy[opt][rs] += lazy[opt][o];
        lazy[opt][o] = 0;
    }
}
void update(int o, int l, int r, int x, int y, int opt, ll v){
    if(l >= x && y >= r){
        val[opt][o] += v;
        lazy[opt][o] += v;
        return ;
    }
    push(o, opt);
    int mid = (l + r) / 2;
    if(mid >= x) update(ls, l, mid, x, y, opt, v);
    if(y > mid) update(rs, mid + 1, r, x, y, opt, v);
}
ll query(int o, int l, int r, int opt, int k){
    if(l == r){
        return val[opt][o];
    }
    push(o, opt);
    int mid = (l + r) / 2;
    if(mid >= k) return query(ls, l, mid, opt, k);
    return query(rs, mid + 1, r, opt, k);
}
int main(){
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    int u, v, opt; ll p;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1, 0, 1);
    build(1, 1, n);
    while(m--){
        scanf("%d", &opt);
        if(opt == 1){
            scanf("%d%lld", &u, &p);
            update(1, 1, n, in[u], out[u], dep[u], p);
            update(1, 1, n, in[u], out[u], dep[u] ^ 1, -p);
        }
        else{
            scanf("%d", &u);
            printf("%lld\n", query(1, 1, n, dep[u], in[u]));
        }
    }
    return 0;
}