XOR-path on tree - MarisaOJ: Marisa Online Judge

XOR-path on tree

Time limit: 1000 ms
Memory limit: 512 MB
Koishi is given a tree $T$, initially rooted at $1$ - the only vertex. She also has $q$ queries, each under the form of 1 in the following 2 types: - $1$. ```Add x y```: Add a vertex and make $x$ its parent, connected by an edge of weight $y$. Denote $|T|$ as the current size of $T$, then this vertex is numbered $|T| + 1$. - $2$. ```Query a b```: Find the maximum $XOR$ path from vertex $a$ to any vertex in the subtree rooted at $b$. It is guaranteed that $1 \le x, a, b \le |T|$ for all queries. Help Koishi find the answer for each query of type $2$. ### Input - The first line contains an integer $q$. - The next $q$ lines, each line contains the information of each query. ### Output - Print the answer for each query of type $2$. ### Constraints - $1 \le q \le 2 \times 10^5$. - $1 \le x, a, b \le |T|$. - $0 \le y \le 2^{30}$. ### Example Input: ``` 4 Add 1 5 Query 1 1 Add 1 7 Query 1 1 ``` Output: ``` 5 7 ```