分析

我们发现题目中需要更改的val只跟深度的奇偶又关系
并且每次更改会影响到的一段dfn区间内的点
所以我们可以用两棵树状数组维护奇数和偶数深度的增量
然后就是区间加和单点查询了
时间复杂度：
期望得分：100分

代码

//CF383C
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

#define ll long long
#define cl(x, y) memset((x), (y), sizeof(x))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define de(x) cerr << #x << " = " << x << " "
#define inc_mod(x, y) x = ((x - y) % mod + mod) % mod
#define add_mod(x, y) x = (x + y) % mod
#define lowbit(x) (x & (-x))
#define inf 0x3f3f3f3f
#define mod 998244353
#define rson (x << 1 | 1)
#define lson (x << 1)
using namespace std;
const int N = 200020;

vector<int> adj[N];
int color[N], vec[N], sz[N], pos[N];
int fro[N];
vector<int> tl;
int n,m;

inline void update(int p, int v) { for(; p <=n; p += lowbit(p)) fro[p] += v; }
inline int get(int p) { int res=0; for(; p; p -= lowbit(p)) res += fro[p]; return res; }

inline int dfs(int u, int prv) {
    int r = 1;
    pos[u] = tl.size();
    tl.push_back(u);
    for(int v:adj[u]) {
        if(v == prv) continue;
        color[v] = !color[u];
        r += dfs(v, u);
    }
    sz[u] = r;
    return r;
}

int main() {
    scanf("%d %d", &n, &m);
    rep(i, 0, n - 1) scanf("%d", vec + i );
    rep(i, 1, n - 1) {
        int u, v;
        scanf("%d %d", &u, &v ); u--;v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    color[0] = 0;
    dfs(0, -1);
    while(m--)
    {
        int op;
        scanf("%d", &op);
        if(op == 1) {
            int x, val;
            scanf("%d %d", &x, &val);
            x--;
            int px = pos[x];
            if(color[x]) val *= -1;
            update(px + 1, val);
            update(px + 1 + sz[x], -val);
        } else {
            int x;
            scanf("%d", &x);
            x--;
            int px = pos[x];
            int r = get(px + 1);
            if(color[x]) r *= -1;
            printf("%d\n", r + vec[x]);
        }
    }
    return 0;
}