Codeforces Round 225 (Div. 1) C. Propagating tree（DFS序，树状数组）

题目链接

Codeforces Round 225 (Div. 1) C. Propagating tree

思路

每一次操作都是对以$u$为根的子树的所有节点进行一次操作，因此我们可以用DFS序来将每一棵子树的所有节点限定到一段连续的区间内。

对于子树内每一个节点是进行加或者减操作，跟树的深度有关（也就是深度的奇偶性）。

因此我们可以用一个树状数组来维护区间和，具体操作可见代码。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
int a[N], depth[N], L[N], R[N], cnt;
vector<int> mp[N];
void dfs(int u, int fu, int deep)
{L[u] = ++cnt;depth[u] = deep;for (int j : mp[u]){if (j == fu) continue;dfs(j, u, deep + 1);}R[u] = cnt;
}
struct BIT
{const static int maxnum = 5e5 + 10;int tree[maxnum];int lowbit(int x){return (x) & (-x);}void add(int idx, int x){for (int pos = idx; pos < maxnum; pos += lowbit(pos)){tree[pos] += x;}}int query(int n){int ans = 0;for (int pos = n; pos; pos -= lowbit(pos)){ans += tree[pos];}return ans;}int query(int a, int b){return query(b) - query(a - 1);}void init(int n){for (int i = 0; i <= n + 2; i++)tree[i] = 0;}
} tree;
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(1, -1, 1);while (m--){int op, x, val;cin >> op >> x;if (op == 1){cin >> val;if (depth[x] & 1) tree.add(L[x], val), tree.add(R[x] + 1, -val);else tree.add(L[x], -val), tree.add(R[x] + 1, val);}else{if (depth[x] & 1)cout << a[x] + tree.query(L[x]) << endl;else cout << a[x] - tree.query(L[x]) << endl;}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}