1256: 经典题
题目
题目描述
开始时，有一个编号为 $1$ 的节点，它是一棵树的根节点。接下来共有 $Q$ 次操作，形如：
Add x y，给树上编号为 $x$ 的节点加一个儿子，新加入的节点和节点 $x$ 之间用一条边权为 $y$ 的边连接，新加入的节点编号等于该节点加入后树上所有的节点数。Query a b，找到从节点 $a$ 出发，到节点 $b$ 的子树中的节点（节点本身也算作在自己的子树中）的最长路径长度。这里路径的长度定义为在路径上所有边权的异或值。
输入格式
第一行一个正整数 $Q$，表示操作数
接下来 $Q$ 行，每行表示一个操作，格式同题目描述
输出格式
对于每个 Query 操作，输出一行一个整数，表示对应答案
样例输入
样例输入 1
text
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
样例输入 2
text
6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4
样例输入 3
text
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
样例输出
样例输出 1
text
5
7
样例输出 2
text
7
2
样例输出 3
text
14
10
13
数据范围
时间限制：5000 ms 空间限制：512 mb
全局限制
- $1 \leq Q\leq 2\times 10^5$
- $x, a, b$ 都是此时存在的节点编号
- $0\leq y \leq 2^{30}$
部分限制
- $(\text{10 points})~Q\leq 200$
- $(\text{20 points})~Q\leq 2\times 10^3$
- $(\text{30 points})~$ 对于所有
Query操作，都保证 $b = 1$ - $(\text{40 points})$ 无限制
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！