18 人解决,24 人已尝试。
31 份提交通过,共有 126 份提交。
5.2 EMB 奖励。
单点时限: 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$ 不为当前的叶子节点)。
若干行,对于每次查询操作,输出一行,一个整数,表示要求的最大路径异或和。
4 A 1 2 Q 1 1 A 1 3 Q 1 1
2 3
18 人解决,24 人已尝试。
31 份提交通过,共有 126 份提交。
5.2 EMB 奖励。
创建: 4 年,1 月前.
修改: 4 年,1 月前.
最后提交: 1 年,5 月前.
来源: N/A