CF1891F A Growing Tree

给定一棵以 $1$ 号结点为根的树，初始时只有一个结点。每个结点都有一个数值，初始为 $0$。现在有 $q$ 个操作，操作分为两种类型： - 第一种操作：向结点 $v$ 添加一个编号为 $sz+1$ 的子结点，其中 $sz$ 表示当前树的结点总数。新结点的数值为 $0$。 - 第二种操作：将 $x$ 加到以结点 $v$ 为根的子树中所有结点的数值上。 所有操作结束后，输出最终树中每个结点的数值。

第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $q$（$1 \leq q \leq 5 \cdot 10^5$），表示操作的数量。 接下来的 $q$ 行，每行描述一个操作： - 第一种操作：第 $i$ 行包含两个整数 $t_i$（$t_i = 1$）、$v_i$。表示向结点 $v_i$ 添加一个编号为 $sz+1$ 的子结点，其中 $sz$ 是当前树的结点总数。保证 $1 \leq v_i \leq sz$。 - 第二种操作：第 $i$ 行包含三个整数 $t_i$（$t_i = 2$）、$v_i$、$x_i$（$-10^9 \leq x_i \leq 10^9$）。表示将 $x_i$ 加到以 $v_i$ 为根的子树中所有结点的数值上。保证 $1 \leq v_i \leq sz$，其中 $sz$ 是当前树的结点总数。 保证所有测试用例中 $q$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出最终树中每个结点的数值。

在第一个样例中，最终树及其结点的数值如下图所示：  最终树及其结点数值。 由 ChatGPT 4.1 翻译