#3244. 「COCI 2020.1」Klasika

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 COCI 2019/2020 Contest #4 T4「Klasika」

开始时,有一个编号为 1 的节点,它代表一棵树的根节点。你的任务是支持以下两种形式的 Q 次操作:

  • \texttt{Add x y} :给树上编号为 x 的节点加一个儿子,新加入的节点和节点 x 之间用一条边权为 y 的边连接,新加入的节点编号等于该节点加入后树上所有的节点数;
  • \texttt{Query a b} :找到从节点 a 出发,到节点 b 的子树中的节点(节点本身也算作在自己的子树中)的最长路径长度。这里路径的长度定义为在路径上所有边权的异或值。

输入格式

第一行一个正整数 Q ,与题目描述中意义相同;

接下来 Q 行,每行表示一个操作,格式同题目描述。

输出格式

对于每个 \texttt{Query} 操作,输出一行一个整数,表示对应答案。

样例

样例输入 1

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

样例输出 1

5
7

样例输入 2

6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

样例输出 2

7
2

样例输入 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\le Q\le 2\times 10^5 ,保证 x,a,b 是在此时刻存在的节点编号, y 不超过 2^{30}

详细子任务限制及分值如下表:

子任务编号 附加限制 分值
1 Q\le 200 10
2 Q\le 2\times 10^3 20
3 对于所有 \texttt{Query} 操作,保证 b=1 30
4 无附加限制 40