CF396C On Changing Tree

CF396C On Changing Tree

给定一棵以 (1) 为根的树，初始时所有点权为 (0)

有 (m) 次操作，分为两种

(1 u x k) 表示给以 (u) 的子树中的每一个点 (v) 点权增加 (x-k imes dis(u, v))

(2 u) 查询点 (u) 的点权模 (10^9+7) 的值

(n, mleq3 imes10^5)

dfs序，树状数组

---

把操作 (1) 中的 (dis(u, v)) 拆成 (dep_v-dep_u) ， (v) 增加的点权即为 (x-k imes(dep_v-dep_u))

即 ((x+k imes dep_u)-(k imes dep_v))

将上式分为 (x+k imes dep_u) 和 (k imes dep_v) 分别维护

(1) 式可以直接用树状数组维护。因为对于每个 (v) ， (dep_v) 是定值，所以 (2) 式可以用树状数组维护每个节点的 (k) 来解决

输出答案时将两式合并即可

时间复杂度 (O(nlog n))

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 10, P = 1e9 + 7;
int n, m, fa[maxn], sz[maxn], tid[maxn], dep[maxn];

inline int inc(int x, int y) {
  return x + y < P ? x + y : x + y - P;
}

inline int dec(int x, int y) {
  return x - y < 0 ? x - y + P : x - y;
}

struct BIT {
  int c[maxn];

  void add(int pos, int x) {
    for (; pos <= n; pos += pos & -pos) {
      c[pos] = inc(c[pos], x);
    }
  }

  int query(int pos) {
    int res = 0;
    for (; pos; pos &= pos - 1) {
      res = inc(res, c[pos]);
    }
    return res;
  }

  void add(int l, int r, int x) {
    add(l, x), add(r + 1, dec(0, x));
  }
} t1, t2;

vector <int> e[maxn];

int dfs(int u) {
  static int now;
  tid[u] = ++now;
  for (int v : e[u]) {
    sz[u] += dfs(v);
  }
  return ++sz[u];
}

int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) {
    scanf("%d", fa + i);
    e[fa[i]].push_back(i);
    dep[i] = dep[fa[i]] + 1;
  }
  dfs(1);
  scanf("%d", &m);
  while (m--) {
    int op, u, x, k;
    scanf("%d %d", &op, &u);
    int l = tid[u], r = tid[u] + sz[u] - 1;
    if (op == 1) {
      scanf("%d %d", &x, &k);
      t1.add(l, r, inc(x, 1ll * dep[u] * k % P));
      t2.add(l, r, k);
    } else {
      printf("%d
", dec(t1.query(l), 1ll * dep[u] * t2.query(l) % P));
    }
  }
  return 0;
}