Problem #3913 - ECNU Online Judge

单点时限: 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 \leq Q \leq 2 \cdot 10^{5}$ ）。

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

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

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

输出格式

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

样例

Input

Output

2
3

18 人解决，24 人已尝试。

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

5.2 EMB 奖励。

创建: 4 年，6 月前.

修改: 2 周，5 天前.

最后提交: 1 年，10 月前.

来源: N/A

3913. 动态树

输入格式

输出格式

样例

服务

开源

关于我们