CF1891F.A Growing Tree

You are given a rooted tree with the root at vertex $1$, initially consisting of a single vertex. Each vertex has a numerical value, initially set to $0$. There are also $q$ queries of two types:

• The first type: add a child vertex with the number $sz + 1$ to vertex $v$, where $sz$ is the current size of the tree. The numerical value of the new vertex will be $0$.
• The second type: add $x$ to the numerical values of all vertices in the subtree of vertex $v$.

After all queries, output the numerical value of all of the vertices in the final tree.

你将得到一棵以顶点 $1$ 为根的有根树，初始时仅包含一个顶点。每个顶点都有一个数值，初始值均为 $0$。此外还有 $q$ 个查询，分为两种类型：

• 第一种类型：向顶点 $v$ 添加一个子顶点，其编号为 $sz + 1$，其中 $sz$ 是当前树的大小（即顶点总数）。新顶点的数值为 $0$。
• 第二种类型：将 $x$ 加到顶点 $v$ 的子树中所有顶点的数值上。

执行完所有查询后，输出最终树中所有顶点的数值。

The first line contains a single integer $T$ ($1 \leq T \leq 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $q$ ($1 \leq q \leq 5 \cdot 10^5$) — the number of queries.

The following $q$ lines can fall into two cases:

• The first type of query: The $i$-th line contains two integers $t_i$ ($t_i = 1$), $v_i$. You need to add a child with the number $sz + 1$ to vertex $v_i$, where $sz$ is the current size of the tree. It is guaranteed that $1 \leq v_i \leq sz$.
• The second type of query: The $i$-th line contains three integers $t_i$ ($t_i = 2$), $v_i$, $x_i$ ($-10^9 \leq x_i \leq 10^9$). You need to add $x_i$ to all numerical values of vertices in the subtree of $v_i$. It is guaranteed that $1 \leq v_i \leq sz$, where $sz$ is the current size of the tree.

It is guaranteed that the sum of $q$ across all test cases does not exceed $5 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output the numerical value of each vertex of the final tree after all queries have been performed.

对于每个测试用例，输出执行完所有查询后最终树中每个顶点的数值。

In the first case, the final tree with the assigned numerical values will look like this:

The final tree with the assigned numerical values

在第一种情况下，分配数值后的最终树形结构如下所示：

分配数值后的最终树形结构