题目描述

难度分:$2000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 5 \times 10^5$。

每组数据输入$q(1 \leq q \leq 5 \times 10^5)$和$q$个操作。

有一棵树，一开始只有一个根节点$1$，点权为$0$。

有两种操作，格式如下：

1. 1 v：在节点$v$的下面添加一个编号为$sz+1$、点权为$0$的儿子，其中$sz$是当前这棵树的大小。
2. 2 v x：把以$v$为根的子树中的所有节点的点权都增加 $x(-10^9 \leq x \leq 10^9)$。

输出所有操作结束后，节点$1,2,3,…,sz$的点权。其中$sz$是最终的树的大小。

输入样例

3
9
2 1 3
1 1
2 2 1
1 1
2 3 2
1 3
2 1 4
1 3
2 3 2
5
2 1 1
1 1
2 1 -1
1 1
2 1 1
5
1 1
1 1
2 1 1
2 1 3
2 2 10

输出样例

7 5 8 6 2 
1 0 1 
4 14 4 

算法

DFS+树状数组

离线来解决这个问题，可以想到当查询节点$u$的答案时，我们希望知道在$u$插入之后的时间中，哪些它的祖先节点（包括它自己）进行过累加$x$的操作？把这些节点累加的$x$求和就是$u$节点的查询结果。

可以先读取所有操作，构建两个结构$rec$、$addT$，同时构建树的邻接表$graph$。$rec[u]$表示节点$u$的加法操作列表，列表中存“（操作时间，本次操作累加的$x$）”二元组。$addT[u]$表示$u$节点插入树中的时间。

然后构建一个树状数组，树状数组的索引代表时间。从根节点$1$开始对树进行DFS，当遍历到$u$节点时，先遍历$rec[u]$，把每个操作累加的$x$按照时间加在树上。由于DFS是自顶向下的，所以进行完这个操作后，$u$往上直到根节点，所有执行过加法操作的节点都被操作完了，在树状数组上查询$(addT[u],q]$的累加和，即为$u$节点的答案。接着递归$u$的所有子节点$v$，递归回来之后还要回溯，将$rec[u]$对树状数组的操作撤销掉，这样才能保证每次遍历到$u$节点的时候，树状数组中只有$u$的祖先节点（包括$u$自己）的操作痕迹。

复杂度分析

设最终树的大小为$n$。

时间复杂度

建图，预处理出$rec$、$addT$两个数组结构的时间复杂度为$O(q)$，即读入所有操作的时间复杂度。

之后DFS求解答案需要遍历整个树，而对子树加$x$的操作需要在树状数组上进行单点加法，还需要查询当前节点的答案，时间复杂度都为$O(log_2n)$。一共有$O(q)$个操作，单点加法会做$O(q)$次，时间复杂度为$O(qlog_2n)$。而对每个节点求答案是区间查询，时间复杂度为$O(log_2n)$，总的时间复杂度为$O(nlog_2n)$。

因此，整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

$rec$的空间消耗为$O(q)$、$addT$和树的邻接表$graph$空间消耗为$O(n)$。对整棵树递归的时候递归深度在最差情况下也是$O(n)$，所以整个算法的额外空间复杂度就是$O(n+q)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int T, q;

class Fenwick {
public:
    explicit Fenwick(int n): sums_(n + 5) {}

    int lowbit(int x) {
        return x&-x;
    }

    void add(int idx, int val) {
        for(++idx; idx < sums_.size(); idx += lowbit(idx)) {
            sums_[idx] += val;
        }
    }

    LL query(int idx) {
        LL ans = 0;
        for(++idx; idx > 0; idx -= lowbit(idx)) {
            ans += sums_[idx];
        }
        return ans;
    }

    LL query(int left, int right) {
        return query(right) - query(left - 1);
    }

private:
    vector<LL> sums_;
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &q);
        int sz = 1;
        unordered_map<int, int> addT;
        unordered_map<int, vector<int>> graph;
        unordered_map<int, vector<PII>> rec;
        for(int ts = 1; ts <= q; ts++) {
            int t, v;
            scanf("%d%d", &t, &v);
            if(t == 1) {
                graph[v].push_back(++sz);
                addT[sz] = ts;
            }else {
                int x;
                scanf("%d", &x);
                rec[v].push_back({ts, x});
            }
        }
        Fenwick tree(q);
        vector<LL> ans(sz + 1);
        function<void(int)> dfs = [&](int u) {
            for(auto&pir: rec[u]) {
                tree.add(pir.first, pir.second);
            }
            ans[u] = tree.query(addT[u] + 1, q);     // 查询时间在addT[u]之后的累加和
            for(int v: graph[u]) {
                dfs(v);
            }
            for(auto&pir: rec[u]) {
                tree.add(pir.first, -pir.second);
            }
        };
        dfs(1);
        for(int node = 1; node <= sz; node++) {
            printf("%lld ", ans[node]);
        }
        puts("");
    }
    return 0;
}