【每日一题】dfs序专题 Propagating tree

Description

给定一棵树，根节点为1，给出两种操作：

1. 查询x节点当前的val
2. 给出x, val, 修改x节点及其子树的值，注意修改过程是随着深度+-+-进行交替的

Solution

首先处理出dfs序，随后单点查询，区间修改可以用差分树状数组来维护。
注意到区间修改的过程是随着深度而改变的，那么不妨开两个树状数组，一个维护奇数层的修改，另一个维护偶数层的修改，不改变原来的权值，只对树状数组进行修改。那么最后的答案就是原来的权值，加上当前奇偶层的修改数，即

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int N = 5e5 + 5;
int depth[N], a[N];
struct Edge {
  int v, nextz;
}edge[N << 1];
int tot, in[N], out[N], head[N], cnt;
void addedge(int u, int v) {
  edge[cnt].v = v;
  edge[cnt].nextz = head[u];
  head[u] = cnt++;
}
void dfs(int u, int par) {
  in[u] = ++tot;
  for(int i = head[u]; ~i; i = edge[i].nextz) {
    int v = edge[i].v;
    if(v == par) continue;
    depth[v] = depth[u] + 1;
    dfs(v, u);
  }
  out[u] = tot;
}
ll T[N][2];
int lowbit(int x) {
  return x & (-x);
}
void update(int x, int add, int id) {
  while(x < N) {
    T[x][id] += add;
    x += lowbit(x);
  }
}
int query(int x, int id) {
  ll res = 0;
  while(x) {
    res += T[x][id];
    x -= lowbit(x);
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; cin >> n >> m;
  memset(head, -1, sizeof(head));
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n - 1; i++) {
    int u, v; cin >> u >> v;
    addedge(u, v);
    addedge(v, u);
  }
  depth[1] = 1;
  dfs(1, -1);
  while(m--) {
    int op, x, val; cin >> op >> x;
    if(op == 1) {
      cin >> val;
      if(depth[x] & 1) {
        update(in[x], val, 1);
        update(out[x] + 1, -val, 1);
        update(in[x], -val, 0);
        update(out[x] + 1, val, 0);
      } else {
        update(in[x], val, 0);
        update(out[x] + 1, -val, 0);
        update(in[x], -val, 1);
        update(out[x] + 1, val, 1);
      }
    } else {
      if(depth[x] & 1)
        cout << a[x] + query(in[x], 1) << '\n';
      else {
        cout << a[x] + query(in[x], 0) << '\n';
      }
    }
  }
  return 0;
}