算法竞赛模板

F. A Growing Tree

很水的一道F

给你一个树根1和q个操作
操作1： 一个数 在某个节点后增加一个节点
操作2： 两个数 把某棵树和它的子树的值都增加x

问q次操作之后每个节点的值分别是多少

dfn序 + 树状数组维护

先建立整棵树，假设所有的节点都存在
记录每个节点遍历到的时间戳和它的子树大小， 之后连续的一段大小必然都是它的子树
然后增加操作就直接把子树范围用树状数组增加， 如果到某个节点了，之前的操作要清空，加上相反数即可清空整棵子树。

这里用BIT add先构建一个差分数组，最后直接O(1)复杂度查询前缀和即是当前点的值

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
struct BIT {
    int n;
    vector<int> a;
    BIT(int _n) {
        n = _n;
        a.assign(n, 0);
    }
    void add(int p, int v) {
        for (; p <= n; p += p & -p) {
            a[p] += v;
        }
    }
    void add(int l, int r, int v) {
        add(l,v);
        if (r < n) { 
            add(r + 1, -v);
        }
    }
    int query(int p) {
        int sum = 0;
        for (; p; p -= p & -p) {
            sum += a[p];
        }
        return sum;
    }
    int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
};
void solve() {
    int n;
    cin >> n;
    struct node {
        int op, v, x, newnode;
    };
    vector<node> q(n*2 + 1);
    vector<int> head(n*2 + 1), nx(4 * n + 10), to(4 * n + 10);
    int id = 1;
    auto ad = [&](int x, int y) {
        to[id] = y;
        nx[id] = head[x];
        head[x] = id++;
    };
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        cin >> q[i].op >> q[i].v;
        if (q[i].op == 2) {
            cin >> q[i].x;
        } else {
            cnt++;
            q[i].newnode = cnt;
            ad(q[i].v, cnt);
        }
    }
    vector<int> dfn(4*n + 10), sz(4*n + 10);
    int ts = 0;
    auto dfs = [&](auto&& self, int cur, int f) -> void {
        dfn[cur] = ++ts;
        sz[cur] = 1;
        for (int i = head[cur]; i; i = nx[i]) {
            // if (to[i] == f) continue;
            self(self,to[i],cur);
            sz[cur] += sz[to[i]];
        }
    };
    dfs(dfs,1,0);
    BIT bit(2*n + 100);
    for (int i = 1; i <= n; i++) {
        if (q[i].op == 2) {
            int cur = q[i].v;
            bit.add(dfn[cur],dfn[cur] + sz[cur] - 1, q[i].x);
        } else {
            int cur = q[i].newnode;
            int val = bit.query(dfn[cur]);
            bit.add(dfn[cur],dfn[cur] + sz[cur] -1, -val);
        }
    }
    for (int i = 1; i <= cnt; i++) {
        cout << bit.query(dfn[i]) << " ";
    }
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}