P7242 [COCI 2019/2020 #4] Klasika

At the beginning, you have a node numbered $1$, which is the root of a tree. Your task is to perform $Q$ operations on the tree. There are two types of operations: - $\texttt{Add x y}$: Add a child to the node numbered $x$ in the tree. The new node’s number is the size of the tree after adding this node, and the edge between it and $x$ has weight $y$. - $\texttt{Query a b}$: Among all paths starting from $a$ to some node in the subtree of node $b$ (including $b$), find the one with the maximum XOR sum of edge weights, and output that XOR sum.

The first line contains an integer $Q$. The next $Q$ lines each contain a string and two numbers, describing one operation.

For each $\texttt{Query}$ operation, output one integer per line representing the answer.

【Constraints and Rules】 | Subtask ID | Special Constraints | Score | | ---------- | ---------------------------------------------------- | ----- | | $1$ | $Q \le 200$ | $10$ | | $2$ | $Q \le 2\times 10^3$ | $20$ | | $3$ | For all $\texttt{Query}$ operations, $b = 1$ is guaranteed. | $30$ | | $4$ | No special constraints. | $40$ | For $100\%$ of the testdata, $1 \le Q \le 2\times 10^5$, $0 \le y \le 2^{30}$, and it is guaranteed that $x, a, b$ are less than or equal to the current size of the tree. 【Hints and Help】 **This problem is translated from [COCI 2019/2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #4](https://hsin.hr/coci/archive/2019_2020/contest4_tasks.pdf) T4 Klasika.** In COCI, this problem is worth $110$ points. Translated by ChatGPT 5