题目
见链接。
题解
知识点：DFS序，树状数组。
我们需要对子树的不同奇偶层加减，用dfn序可以解决子树问题，但是并不能直接分奇偶。
一种比较麻烦的思路是，将dfn序分成两个序列，一个是偶数层点序，一个是奇数层点序列，处理两个序列对于某个点作为子树根节点时，开始和结束节点，然后就可以用线段树分别处理差分。
但实际上，我们不需要对dfn序分离，只需要用两个完整的dfn序，分别统计对奇偶层的改变，每次修改同时修改两个序列的完整子树的差分，但加减不同即可。
其中，两个序列会出现不应该存在的点，比如对于统计偶数层的dfn序出现的奇数层点，那么直接对一个序列做完整子树的修改，会对它们产生错误的修改，但这是无关紧要的。因为我们查询的是单点权值，只要确定我们查询的那个点的奇偶性，去应该出现他的dfn序里查询即可，不存在的点是无法影响答案的。
如果问题改成求一个子树的权值和，那么这种方法就不行了，第一是没法方便的求出一个子树的权值和，因为奇偶层没有分离；第二是对不存在的点做了错误修改，只能用第一种麻烦的方法。
时间复杂度 \(O(n+m\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Graph {
struct edge {
int v, nxt;
};
int idx;
vector<int> h;
vector<edge> e;
Graph(int n = 0, int m = 0) { init(n, m); }
void init(int n, int m) {
idx = 0;
h.assign(n + 1, 0);
e.assign(m + 1, {});
}
void add(int u, int v) {
e[++idx] = { v,h[u] };
h[u] = idx;
}
};
struct T {
int sum;
static T e() { return { 0 }; }
T &operator+=(const T &x) { return sum += x.sum, *this; }
};
template<class T>
struct Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T::e());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T::e();
for (int i = x;i >= 1;i -= i & -i) ans += node[i];
return ans;
}
};
const int N = 200007;
Graph g;
int a[N];
int dfncnt;
int L[N], R[N], dep[N];
void dfs(int u, int fa) {
L[u] = ++dfncnt;
dep[u] = dep[fa] + 1;
for (int i = g.h[u];i;i = g.e[i].nxt) {
int v = g.e[i].v;
if (v == fa) continue;
dfs(v, u);
}
R[u] = dfncnt;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
g.init(n, n << 1);
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n - 1;i++) {
int u, v;
cin >> u >> v;
g.add(u, v);
g.add(v, u);
}
dfs(1, 0);
Fenwick<T> fw[2] = { Fenwick<T>(n),Fenwick<T>(n) };
while (m--) {
int op, x;
cin >> op >> x;
if (op == 1) {
int val;
cin >> val;
bool odd = dep[x] & 1;
fw[odd].update(L[x], { val });
fw[odd].update(R[x] + 1, { -val });
fw[odd ^ 1].update(L[x], { -val });
fw[odd ^ 1].update(R[x] + 1, { val });
//! 单点查询可以[L,R]区间加，因为不存在的点不会影响答案
//! 但如果求子树权值和，那只能一开始就把dfs序按深度奇偶性分开，用线段树维护，操作很复杂
}
else cout << a[x] + fw[dep[x] & 1].query(L[x]).sum << '\n';
}
return 0;
}