310814: CF1891F. A Growing Tree
Description
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.
InputThe 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$.
OutputFor each test case, output the numerical value of each vertex of the final tree after all queries have been performed.
ExampleInput3 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 10Output
7 5 8 6 2 1 0 1 4 14 4Note
In the first case, the final tree with the assigned numerical values will look like this:
Output
你有一个以顶点1为根的树,最初只包含一个顶点。每个顶点都有一个数值,最初设置为0。有q个查询,分为两种类型:
1. 第一种类型:在顶点v上添加一个子顶点,顶点编号为sz+1,其中sz是当前树的大小。新顶点的数值为0。
2. 第二种类型:将x加到顶点v的子树中所有顶点的数值上。
在所有查询之后,输出最终树中所有顶点的数值。
输入数据格式:
第一行包含一个整数T(1≤T≤10^4),表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数q(1≤q≤5×10^5),表示查询的数量。接下来的q行分为两种情况:
- 第一种查询:第i行包含两个整数t_i(t_i=1)和v_i。需要在顶点v_i上添加一个子顶点,顶点编号为sz+1,其中sz是当前树的大小。保证1≤v_i≤sz。
- 第二种查询:第i行包含三个整数t_i(t_i=2)、v_i和x_i(-10^9≤x_i≤10^9)。需要将x_i加到顶点v_i的子树中所有顶点的数值上。保证1≤v_i≤sz,其中sz是当前树的大小。
保证所有测试用例的q之和不超过5×10^5。
输出数据格式:
对于每个测试用例,输出所有查询执行后最终树中每个顶点的数值。题目大意: 你有一个以顶点1为根的树,最初只包含一个顶点。每个顶点都有一个数值,最初设置为0。有q个查询,分为两种类型: 1. 第一种类型:在顶点v上添加一个子顶点,顶点编号为sz+1,其中sz是当前树的大小。新顶点的数值为0。 2. 第二种类型:将x加到顶点v的子树中所有顶点的数值上。 在所有查询之后,输出最终树中所有顶点的数值。 输入数据格式: 第一行包含一个整数T(1≤T≤10^4),表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数q(1≤q≤5×10^5),表示查询的数量。接下来的q行分为两种情况: - 第一种查询:第i行包含两个整数t_i(t_i=1)和v_i。需要在顶点v_i上添加一个子顶点,顶点编号为sz+1,其中sz是当前树的大小。保证1≤v_i≤sz。 - 第二种查询:第i行包含三个整数t_i(t_i=2)、v_i和x_i(-10^9≤x_i≤10^9)。需要将x_i加到顶点v_i的子树中所有顶点的数值上。保证1≤v_i≤sz,其中sz是当前树的大小。 保证所有测试用例的q之和不超过5×10^5。 输出数据格式: 对于每个测试用例,输出所有查询执行后最终树中每个顶点的数值。