3913. 动态树

单点时限: 4.0 sec

内存限制: 1024 MB

你需要维护一棵动态树,初始状态下仅有一个节点,编号为 $1$,并支持以下操作:

Add x y:插入一个节点,其编号为当前存在的节点数量(包括当前新加入的节点),指定其父节点为 $x$,并添加一条无向边连接新节点和它的父节点,边权为 $y$。

Query x y:查询起点为 $x$ 号节点,终点在 $y$ 的子树中(包括 $y$ 号节点)的最大简单路径异或和(要求路径不经过重复的节点,且起点与终点不同)。若一条路径上所有边的边权分别为 $a_1,a_2,\dots,a_k$,则路径异或和为 $a_1 \oplus a_2 \oplus \dots \oplus a_k$。其中 $\oplus$ 为按位异或操作,它在 C++、Java 等语言中以 ^ 来表示。

输入格式

第一行,一个正整数 $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$ 不为当前的叶子节点)。

输出格式

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

样例

Input
4
A 1 2
Q 1 1
A 1 3
Q 1 1
Output
2
3

18 人解决,24 人已尝试。

31 份提交通过,共有 126 份提交。

5.2 EMB 奖励。

创建: 4 年,1 月前.

修改: 4 年,1 月前.

最后提交: 1 年,5 月前.

来源: N/A

题目标签