ECNU XCPC 2021 November Training #2

输入格式

第一行，一个正整数 $Q$（$1\le Q\le 2\cdot {10}^5$）。

接下来 $Q$ 行，每行依次输入一个字符 $opt$ 和两个整数 $x,y$。

若 $opt=$A，插入一个节点，其编号为当前存在的节点数量（包括当前新加入的节点），其父节点为 $x$，边权为 $y$。（$0\le y\le 2^{30}$，数据确保 $x$ 为之前已插入的节点编号）。

若 $opt=$Q，查询起点为 $x$ 号节点，终点在 $y$ 的子树中的最大简单路径异或和（数据确保 $x,y$ 为已存在的节点编号，且至少存在一条合法的简单路径使得起点与终点不同。换言之，当 $x=y$ 时，数据确保 $x$ 不为当前的叶子节点）。

输出格式

若干行，对于每次查询操作，输出一行，一个整数，表示要求的最大路径异或和。

4
A 1 2
Q 1 1
A 1 3
Q 1 1

2
3