A11631. Tree
编程题
普及/提高-
知识点
题目描述
First line containing the number of queries $Q$ $(1<=Q<=400000)$ .
Let $last$ be the answer for previous query of type $2$ (initially $last$ equals $0$ ).
Each of the next $Q$ lines contains a query of following form:
- 1 p q ( $1<=p,q<=10^{18}$ ): This is query of first type where  and . It is guaranteed that $1<=R<=cnt$ and $0<=W<=10^{9}$ .
- 2 p q ( $1<=p,q<=10^{18}$ ): This is query of second type where  and . It is guaranteed that $1<=R<=cnt$ and $0<=X<=10^{15}$ .
 denotes bitwise XOR of $a$ and $b$ .
It is guaranteed that at least one query of type 2 exists.
Let $last$ be the answer for previous query of type $2$ (initially $last$ equals $0$ ).
Each of the next $Q$ lines contains a query of following form:
- 1 p q ( $1<=p,q<=10^{18}$ ): This is query of first type where  and . It is guaranteed that $1<=R<=cnt$ and $0<=W<=10^{9}$ .
- 2 p q ( $1<=p,q<=10^{18}$ ): This is query of second type where  and . It is guaranteed that $1<=R<=cnt$ and $0<=X<=10^{15}$ .
 denotes bitwise XOR of $a$ and $b$ .
It is guaranteed that at least one query of type 2 exists.
输入格式
Output the answer to each query of second type in separate line.
输出格式
In the first example,
$last=0$
\- Query 1: 1 1 1, Node $2$ with weight $1$ is added to node $1$ .
\- Query 2: 2 2 0, No sequence of nodes starting at $2$ has weight less than or equal to $0$ . $last=0$
\- Query 3: 2 2 1, Answer is $1$ as sequence will be ${2}$ . $last=1$
\- Query 4: 1 2 1, Node $3$ with weight $1$ is added to node $2$ .
\- Query 5: 2 3 1, Answer is $1$ as sequence will be ${3}$ . Node $2$ cannot be added as sum of weights cannot be greater than $1$ . $last=1$
\- Query 6: 2 3 3, Answer is $2$ as sequence will be ${3,2}$ . $last=2$
$last=0$
\- Query 1: 1 1 1, Node $2$ with weight $1$ is added to node $1$ .
\- Query 2: 2 2 0, No sequence of nodes starting at $2$ has weight less than or equal to $0$ . $last=0$
\- Query 3: 2 2 1, Answer is $1$ as sequence will be ${2}$ . $last=1$
\- Query 4: 1 2 1, Node $3$ with weight $1$ is added to node $2$ .
\- Query 5: 2 3 1, Answer is $1$ as sequence will be ${3}$ . Node $2$ cannot be added as sum of weights cannot be greater than $1$ . $last=1$
\- Query 6: 2 3 3, Answer is $2$ as sequence will be ${3,2}$ . $last=2$
输入输出样例
输入 #1
6 1 1 1 2 2 0 2 2 1 1 3 0 2 2 0 2 2 2
输出 #1
0 1 1 2
输入 #2
6 1 1 0 2 2 0 2 0 3 1 0 2 2 1 3 2 1 6
输出 #2
2 2 3 2
输入 #3
7 1 1 2 1 2 3 2 3 3 1 0 0 1 5 1 2 5 0 2 4 0
输出 #3
1 1 2
输入 #4
7 1 1 3 1 2 3 2 3 4 1 2 0 1 5 3 2 5 5 2 7 22
输出 #4
1 2 3
说明/提示
In the first example,
$last=0$
\- Query 1: 1 1 1, Node $2$ with weight $1$ is added to node $1$ .
\- Query 2: 2 2 0, No sequence of nodes starting at $2$ has weight less than or equal to $0$ . $last=0$
\- Query 3: 2 2 1, Answer is $1$ as sequence will be ${2}$ . $last=1$
\- Query 4: 1 2 1, Node $3$ with weight $1$ is added to node $2$ .
\- Query 5: 2 3 1, Answer is $1$ as sequence will be ${3}$ . Node $2$ cannot be added as sum of weights cannot be greater than $1$ . $last=1$
\- Query 6: 2 3 3, Answer is $2$ as sequence will be ${3,2}$ . $last=2$
$last=0$
\- Query 1: 1 1 1, Node $2$ with weight $1$ is added to node $1$ .
\- Query 2: 2 2 0, No sequence of nodes starting at $2$ has weight less than or equal to $0$ . $last=0$
\- Query 3: 2 2 1, Answer is $1$ as sequence will be ${2}$ . $last=1$
\- Query 4: 1 2 1, Node $3$ with weight $1$ is added to node $2$ .
\- Query 5: 2 3 1, Answer is $1$ as sequence will be ${3}$ . Node $2$ cannot be added as sum of weights cannot be greater than $1$ . $last=1$
\- Query 6: 2 3 3, Answer is $2$ as sequence will be ${3,2}$ . $last=2$