CF396C On Changing Tree https://codeforces.com/problemset/problem/396/C
给定一棵以 \(1\) 为根的树, 初始时所有点权为 \(0\)
有 \(m\) 次操作, 分为两种
\(1\ u\ x\ k\) 表示给以 \(u\) 的子树中的每一个点 \(v\) 点权增加 \(x-k\times dis(u,\ v)\)
\(2\ u\) 查询点 \(u\) 的点权模 \(10^9+7\) 的值
\(n,\ m\leq3\times10^5\)
dfs 序, 树状数组
把操作 \(1\) 中的 \(dis(u,\ v)\) 拆成 \(dep_v-dep_u\) , \(v\) 增加的点权即为 \(x-k\times(dep_v-dep_u)\)
即 \((x+k\times dep_u)-(k\times dep_v)\)
将上式分为 \(x+k\times dep_u\) 和 \(k\times dep_v\) 分别维护
\(1\) 式可以直接用树状数组维护. 因为对于每个 \(v\) , \(dep_v\) 是定值, 所以 \(2\) 式可以用树状数组维护每个节点的 \(k\) 来解决
输出答案时将两式合并即可
时间复杂度 \(O(n\log 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\n", dec(t1.query(l), 1ll * dep[u] * t2.query(l) % P));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3039147.html