题目描述
开始时,你有一个编号为 $1$ 的节点,它代表着一棵树的根。你的任务对树进行 $Q$ 次操作。
操作分为两类:
- $\texttt{Add x y}$,给树上编号为 $x$ 的节点加入一个儿子,该儿子的编号为加入该节点后树的大小,它与 $x$ 的边的边权为 $y$。
- $\texttt{Query a b}$,查找从 $a$ 出发,到 $b$ 节点子树内某个节点(包括 $B$ )的路径中边权异或和最大的一条,并输出其异或和。
输入格式
第一行一个整数 $Q$。
加下来 $Q$ 行,每行一个字符串和两个数字,描述一次操作。
输出格式
对于每个 $\texttt{Query}$ 操作,一行一个整数表示答案。
样例 #1
样例输入 #1
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
样例输出 #1
5
7
样例 #2
样例输入 #2
6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4
样例输出 #2
7
2
样例 #3
样例输入 #3
10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3
样例输出 #3
14
10
13
提示
【数据规模与约定】
子任务编号 | 特殊限制 | 分值 |
---|---|---|
$1$ | $Q\le 200$ | $10$ |
$2$ | $Q\le 2\times 10^3$ | $20$ |
$3$ | 对于所有 $\texttt{Query}$ 操作,保证 $b=1$ | $30$ |
$4$ | 无特殊限制 | $40$ |
对于 $100\%$ 的数据,$1\le Q\le 2\times 10^5$,$0\le y\le 2^{30}$,保证 $x,a,b$ 小于等于当前树的大小。