Problem Description

You are given a weighted tree with $N$ vertices, numbered from $0$ to $N - 1$. For each $i$ with $1 \le i \le N - 1$, vertex $i$ is connected to its parent vertex $P[i]$ ($P[i] < i$) by an edge with weight $W[i]$ ($W[i] \ge 0$). Note that vertex $0$ has no parent; for convenience, we set $P[0] = W[0] = -1$.

The only way for Sasaki to move on the tree is by teleportation. Sasaki can teleport from vertex $u$ to vertex $v$ using $e$ energy if and only if all of the following conditions hold:

• $u$ is an ancestor of $v$, or $v$ is an ancestor of $u$, and
• the bitwise XOR sum of all edge weights on the path from $u$ to $v$ is at most $e$.

Note: Each teleport does not consume energy; after each teleport, Sasaki still has $e$ energy.

::::info[When is $u$ an ancestor of $v$?]{open} Vertex $u$ is an ancestor of vertex $v$ if at least one of the following is true:

• Vertex $u$ is vertex $v$ itself ($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
• and so on. ::::

::::info[What is the bitwise XOR sum (XOR)?]{open} The bitwise XOR sum of two non-negative integers $a$ and $b$ (denoted by $a \oplus b$) is defined as follows:

• When $a \oplus b$ is written in binary, for the digit at $2^k$, the result is $1$ if exactly one of $a$ and $b$ has a $1$ at that digit; otherwise it is $0$.

For example:

• $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (in binary: $100 \oplus 10101 = 10001$).

The bitwise XOR of multiple integers $A[0], A[1], ..., A[K - 1]$ is defined as $A[0] \oplus A[1] \oplus A[2] \oplus ... \oplus A[K - 1]$.

Note that $\oplus$ is commutative and associative. That is, $a \oplus b = b \oplus a$ and $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. Therefore, the final result does not depend on the order of the integers or the order of the XOR operations. ::::

Miyako needs to answer $Q$ queries. Each query is specified by a pair of integers $U$ and $V$. Miyako's task is to compute the minimum energy required for Sasaki to reach vertex $V$ from vertex $U$ using zero or more teleport operations.

Implementation Details

You need to implement the following functions:

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

• $N$: the number of vertices in the tree.
• $P, W$: integer arrays of length $N$ that specify each vertex's parent and the connecting edge weight, respectively.
• This function is called exactly once at the beginning (before any calls to minimum_energy).

int minimum_energy(int U, int V)

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

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]

Here, $U[j]$ and $V[j]$ (for all $0 \le j < Q$) are the input parameters of the $j$-th call to minimum_energy.

Output Format

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

Here, $A[j]$ is the answer to the $j$-th query (for all $0 \le j < Q$).

Hint

Samples

Consider the following function call:

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

This tree has $6$ vertices, as shown in the figure below.

:::align{center} :::

minimum_energy(2, 4)

Sasaki can use the following teleports, requiring $1$ energy to move from vertex $2$ to vertex $4$:

• Teleport from vertex $2$ to vertex $0$. Vertex $0$ is an ancestor of vertex $2$, and the bitwise XOR sum of edge weights on the path 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 sum of edge weights on the path from vertex $0$ to vertex $4$ is $3 \oplus 2 = 1$.

There is no teleport sequence that uses strictly less energy. Therefore, this call should return $1$.

minimum_energy(3, 0)

Sasaki can use the following teleport, requiring $0$ energy to move from vertex $3$ to vertex $0$:

• Teleport from vertex $3$ to vertex $0$. Vertex $0$ is an ancestor of vertex $3$, and the bitwise XOR sum of edge weights on the path from vertex $3$ to vertex $0$ is $0$.

Therefore, this call should return $0$.

minimum_energy(1, 1)

Since both the start and the destination are vertex $1$, Sasaki does not need to teleport at all, so the required energy is zero. Therefore, this call should return $0$.

minimum_energy(0, 5)

Sasaki can use the following teleport, requiring $0$ energy to move from vertex $0$ to vertex $5$:

• Teleport from vertex $0$ to vertex $5$. Vertex $0$ is an ancestor of vertex $5$, and the bitwise XOR sum of edge weights on the path from vertex $0$ to vertex $5$ is $3 \oplus 2 \oplus 1 = 0$.

Therefore, this call should return $0$.

Constraints

• $2 \le N \le 50\ 000$.
• $1 \le Q \le 100\ 000$。
• $P[0] = -1$.
• For all $0 \le i < N$, $0 \le P[i] < i$.
• $W[0] = -1$.
• For all $0 \le i < N$, $0 \le W[i] < 2^{20}$.
• In each query, $0 \le U, V < N$.

Subtasks

1. ($5$ points) $N \le 10$.
2. ($9$ points) For all $0 \le i < N$, $W[i] \le 1$.
3. ($15$ points) $N \le 200$.
4. ($0$ points) Same as above.
5. ($28$ points) For all $0 \le i < N$, $W[i] < 128$.
6. ($28$ points) $N \le 10\ 000$.
7. ($15$ points) No additional constraints.

Translated by ChatGPT 5