Skip to content

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}$

部分限制

  1. $(\text{10 points})~Q\leq 200$
  2. $(\text{20 points})~Q\leq 2\times 10^3$
  3. $(\text{30 points})~$ 对于所有Query 操作,都保证 $b = 1$
  4. $(\text{40 points})$ 无限制

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!