XOR-path on tree - MarisaOJ: Marisa Online Judge

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$

Topic

Graph

STL

Rating

2000

Solution (0)

Solution