Logo Universal Online Judge

UOJ

时间限制:5 s 空间限制:512 MB
Statistics

题目描述

开始时,你有一个编号为 $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$ 小于等于当前树的大小。