P7242 [COCI 2019/2020 #4] Klasika

开始时，你有一个编号为 $1$ 的节点，它代表着一棵树的根。你的任务是对树进行 $Q$ 次操作。 操作分为两类： - $\texttt{Add x y}$，给树上编号为 $x$ 的节点加入一个儿子，该儿子的编号为加入该节点后树的大小，它与 $x$ 的边的边权为 $y$。 - $\texttt{Query a b}$，查找从 $a$ 出发，到 $b$ 节点子树内某个节点（包括 $B$ ）的路径中边权异或和最大的一条，并输出其异或和。

第一行一个整数 $Q$。 加下来 $Q$ 行，每行一个字符串和两个数字，描述一次操作。

对于每个 $\texttt{Query}$ 操作，一行一个整数表示答案。

【数据规模与约定】 | 子任务编号 | 特殊限制 | 分值 | | ---------- | ------------------------------------------ | ---- | | $1$ | $Q\le 200$ | $10$ | | $2$ | $Q\le 2\times 10^3$ | $20$ | | $3$ | 对于所有 $\texttt{Query}$ 操作，保证 $b=1$ | $30$ | | $4$ | 无特殊限制 | $40$ | 对于 $100\%$ 的数据，$1\le Q\le 2\times 10^5$，$0\le y\le 2^{30}$，保证 $x,a,b$ 小于等于当前树的大小。 【提示与帮助】 **题目译自 [COCI 2019/2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #4](https://hsin.hr/coci/archive/2019_2020/contest4_tasks.pdf) T4 Klasika** 在 COCI 中，本题分值为 $110$ 分。