P16705 [SEATST 2026] XOR Teleport / XOR Teleport

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: ```cpp void init(int N, std::vector P, std::vector 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`). ```cpp 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.

``` 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`.

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

### Samples Consider the following function call: ```cpp 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}  ::: ```cpp 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$. ```cpp 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$. ```cpp 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$. ```cpp 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