Description

There is an edge-weighted tree consisting of $N$ vertices, numbered from $0$ to $N - 1$. For every $i$, such that $1 \leq i \leq N-1$, vertex $i$ is connected to its parent $P[i]$ ($P[i] < i$) with an edge of weight $W[i]$ ($W[i] \geq 0$). Note that vertex $0$ does not have a parent and therefore for convenience, we set $P[0] = W[0] = -1$.

Sasaki's only way of moving between vertices of the tree is through teleportation. With energy $e$, Sasaki can teleport from vertex $u$ to vertex $v$ if and only if all of the following are satisfied.

• Either $u$ is an ancestor of $v$, or $v$ is an ancestor of $u$, AND
• The bitwise XOR of all the weight of edges from $u$ to $v$ is at most $e$.

Note that teleportation does not consume any energy; Sasaki still has energy $e$ after each teleportation.

When is $u$ an ancestor of $v$? Vertex $u$ is an ancestor of $v$ if at least one of the following conditions is true:

• vertex $u$ is vertex $v$ ($u = v$), OR
• vertex $u$ is the parent of vertex $v$ ($u = P[v]$), OR
• vertex $u$ is the parent of the parent of vertex $v$ ($u = P[P[v]]$), OR
• vertex $u$ is the parent of the parent of the parent of vertex $v$ ($u = P[P[P[v]]]$), OR
• etc

What is bitwise XOR? The bitwise XOR of two non-negative integers $a$ and $b$, denoted as $a \oplus b$, is defined as follows: - When $a \oplus b$ is written in base two, the digit in the $2^k$'s place is $1$ if exactly one of the digits in the $2^k$'s place of $a$ and $b$ is $1$, and $0$ otherwise. For example:

• $3 \oplus 5 = 6$ (in base two: $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (in base two: $100 \oplus 10101 = 10001$). The bitwise XOR of multiple integers $A[0], A[1], \ldots, A[K-1]$ is defined as $A[0] \oplus A[1] \oplus A[2] \oplus \ldots \oplus A[K-1]$. Note that $\oplus$ is a commutative and associative operator. That is, $a \oplus b = b \oplus a$ and $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ respectively. So it does not matter in what order we arrange the integers, and it does not matter in what order we apply XOR to the integers to obtain the final bitwise XOR.

Miyano has to answer $Q$ queries. Each query is specified using a pair of integers $U$ and $V$. Miyano's task is to calculate the minimum energy Sasaki needs to go from vertex $U$ to vertex $V$ using zero or more teleport operations.

Implementation Details

You should implement the following procedure.

void init(int N, std::vector<int> P, std::vector<int> W)

• $N$: the number of vertices of the tree.
• $P$, $W$: arrays of integers of length $N$ specifying the parents of each vertex and the weight of the edge connecting them.
• This procedure is called exactly once in the beginning, before any calls to minimum_energy.

int minimum_energy(int U, int V)

• $U$, $V$: the pair of integers describing a query.
• This procedure is called exactly $Q$ times after the invocation of init.
• This procedure should return the answer to the given query.

Constraints

• $2 \leq N \leq 50\;000$.
• $1 \leq Q \leq 100\;000$.
• $P[0] = -1$.
• $0 \leq P[i] < i$, for all $0 \leq i < N$.
• $W[0] = -1$.
• $0 \leq W[i] < 2^{20}$, for all $0 \leq i < N$.
• $0 \leq U, V < N$ in each query.

Subtasks

1. (5 points) $N \leq 10$.
2. (9 points) $W[i] \leq 1$, for all $0 \leq i < N$.
3. (15 points) $N \leq 200$.
4. (28 points) $W[i] < 128$, for all $0 \leq i < N$.
5. (28 points) $N \leq 10\;000$.
6. (15 points) No additional constraints.

Example

Consider the following calls.

init(6, [-1, 0, 1, 0, 1, 2], [-1, 3, 2, 0, 2, 1])

The tree consists of $6$ vertices, which can be illustrated below.

minimum_energy(2, 4)

Sasaki can move from vertex $2$ to vertex $4$ with energy $1$ by using the teleports as follows:

• Teleport from vertex $2$ to vertex $0$. Vertex $0$ is an ancestor of vertex $2$ and the bitwise-XOR of the weight of edges from vertex $2$ to vertex $0$ is $2 \oplus 3 = 1$.
• Teleport from vertex $0$ to vertex $4$. Vertex $0$ is an ancestor of vertex $4$ and the bitwise-XOR of the weight of edges from vertex $0$ to vertex $4$ is $3 \oplus 2 = 1$.

There are no other sequences of teleports that use strictly less energy. Therefore, this call should return $1$.

minimum_energy(3, 0)

Sasaki can move from vertex $3$ to vertex $0$ with energy $0$ by using the teleports as follows:

• Teleport from vertex $3$ to vertex $0$. Vertex $0$ is an ancestor of vertex $3$ and the bitwise-XOR of the weight of edges from vertex $3$ to vertex $0$ is $0$.

Therefore, this call should return $0$.

minimum_energy(1, 1)

Since the start and end vertices are both vertex $1$, Sasaki does not need to do any teleports, which requires zero energy. Therefore, this call should return $0$.

minimum_energy(0, 5)

Sasaki can move from vertex $0$ to vertex $5$ with energy $0$ by using the teleports as follows:

• Teleport from vertex $0$ to vertex $5$. Vertex $0$ is an ancestor of vertex $5$ and the bitwise-XOR of the weight of edges from vertex $0$ to vertex $5$ is $3 \oplus 2 \oplus 1 = 0$.

Therefore, this call should return $0$.

Sample Grader

Input format:

N
P[1] P[2] ... P[N - 1]
W[1] W[2] ... W[N - 1]
Q
U[0] V[0]
U[1] V[1]
...
U[Q - 1] V[Q - 1]

where $U[j]$ and $V[j]$, for all $0 \leq j < Q$, are the input arguments for the $j$-th call to minimum_energy.

Output format:

A[0]
A[1]
...
A[Q - 1]

where $A[j]$ is the answer to query $j$, for each $j$ such that $0 \leq j < Q$.