P16705 [SEATST 2026] XOR 传送 / XOR Teleport

给定一棵包含 $N$ 个顶点的带边权树，顶点编号从 $0$ 到 $N - 1$。对于每个满足 $1 \le i \le N - 1$ 的 $i$ ，顶点 $i$ 与其父顶点 $P[i]$ （$P[i] < i$）相连，边权为 $W[i]$ （$W[i] \ge 0$）。请注意，顶点 $0$ 没有父节点，为了方便起见，我们设 $P[0] = W[0] = -1$。 Sasaki 在树上移动的唯一方式是通过传送。Sasaki 可以透过 $e$ 个能量从顶点 $u$ 传送到顶点 $v$ 当且仅当同时满足以下所有条件： - $u$ 是 $v$ 的祖先，或者 $v$ 是 $u$ 的祖先，并且 - 从 $u$ 到 $v$ 路径上所有边权的按位异或和（XOR）不超过 $e$。 **注意**：每次的传送不消耗能量；每次的传送后，Sasaki 还是有 $e$ 个能量 ::::info[什么时候 $u$ 是 $v$ 的祖先？]{open} 如果以下至少一个条件为真，则顶点 $u$ 是顶点 $v$ 的祖先： - 顶点 $u$ 就是顶点 $v$ （$u = v$），或者 - 顶点 $u$ 是顶点 $v$ 的父节点（$u = P[v]$），或者 - 顶点 $u$ 是顶点 $v$ 的父节点的父节点（$u = P[P[v]]$），或者 - 顶点 $u$ 是顶点 $v$ 的父节点的父节点的父节点（$u = P[P[P[v]]]$），或者 - 依此类推。 :::: ::::info[什么是按位异或和（XOR）？]{open} 两个非负整数 $a$ 和 $b$ 的按位异或和（记为 $a \oplus b$ ）定义如下： - 当 $a \oplus b$ 写为二进制时，如果 $a$ 和 $b$ 在 $2^k$ 位的数字恰好有一个为 $1$，则该位的结果为 $1$，否则为 $0$。 例如： - $3 \oplus 5 = 6$ （二进制表示：$011 \oplus 101 = 110$）。 - $4 \oplus 21 = 17$ （二进制表示：$100 \oplus 10101 = 10001$）。 多个整数 $A[0], A[1], ..., A[K - 1]$ 的按位异或定义为 $A[0] \oplus A[1] \oplus A[2] \oplus ... \oplus A[K - 1]$。 注意 $\oplus$ 是满足交换律和结合律的运算符。也就是说，$a \oplus b = b \oplus a$ 和 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$。因此，以何种顺序排列这些整数或者以何种顺序进行异或运算并不影响最终的结果。 :::: Miyako 需要回答 $Q$ 个询问。每个询问由一对整数 $U$ 和 $V$ 指定。Miyako 的任务是计算 Sasaki 使用零次或多次传送操作从顶点 $U$ 到达顶点 $V$ 所需的 **最小能量**。 ### 实现详情 你需要实现以下函数： ```cpp void init(int N, std::vector P, std::vector W) ``` - $N$：树的顶点数量。 - $P, W$：长度为 $N$ 的整数数组，分别指定每个顶点的父节点和连接它们的边权。 - 此函数在开始时（在调用任何 `minimum_energy` 之前）恰好被调用一次。 ```cpp int minimum_energy(int U, int V) ``` - $U, V$：描述一次询问的一对整数。 - 此函数在调用 `init` 后恰好被调用 $Q$ 次。 - 此函数应返回给定询问的答案。

``` 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] ``` 其中 $U[j]$ 和 $V[j]$ （对于所有 $0 \le j < Q$ ）是第 $j$ 次调用 `minimum_energy` 的输入参数。

``` A[0] A[1] ... A[Q - 1] ``` 其中 $A[j]$ 是第 $j$ 次询问的答案（对于所有 $0 \le j < Q$）。

### 样例 考虑以下函数调用： ```cpp init(6, [-1, 0, 1, 0, 1, 2], [-1, 3, 2, 0, 2, 1]) ``` 这棵树包含 $6$ 个顶点，如下图所示。 :::align{center}  ::: ```cpp minimum_energy(2, 4) ``` Sasaki 可以使用以下传送方式，需要 $1$ 个能量从顶点 $2$ 移动到顶点 $4$： - 从顶点 $2$ 传送到顶点 $0$。顶点 $0$ 是顶点 $2$ 的祖先，且从顶点 $2$ 到顶点 $0$ 路径上的边权按位异或和为 $2 \oplus 3 = 1$ 。 - 从顶点 $0$ 传送到顶点 $4$。顶点 $0$ 是顶点 $4$ 的祖先，且从顶点 $0$ 到顶点 $4$ 路径上的边权按位异或和为 $3 \oplus 2 = 1$ 。 不存在透过能量严格更少的传送序列。因此，该调用应返回 $1$。 ```cpp minimum_energy(3, 0) ``` Sasaki 可以使用以下传送方式，需要 $0$ 个能量从顶点 $3$ 移动到顶点 $0$： - 从顶点 $3$ 传送到顶点 $0$。顶点 $0$ 是顶点 $3$ 的祖先，且从顶点 $3$ 到顶点 $0$ 路径上的边权按位异或和为 $0$。 因此，该调用应返回 $0$。 ```cpp minimum_energy(1, 1) ``` 由于起点和终点都是顶点 $1$， Sasaki 不需要进行任何传送，需要的能量为零。因此，该调用应返回 $0$。 ```cpp minimum_energy(0, 5) ``` Sasaki 可以使用以下传送方式，需要 $0$ 个能量从顶点 $0$ 移动到顶点 $5$： - 从顶点 $0$ 传送到顶点 $5$。顶点 $0$ 是顶点 $5$ 的祖先，且从顶点 $0$ 到顶点 $5$ 路径上的边权按位异或和为 $3 \oplus 2 \oplus 1 = 0$。 因此，该调用应返回 $0$。 ### 约束 - $2 \le N \le 50\ 000$。 - $1 \le Q \le 100\ 000$。 - $P[0] = -1$。 - 对于所有 $0 \le i < N$， $0 \le P[i] < i$。 - $W[0] = -1$。 - 对于所有 $0 \le i < N$， $0 \le W[i] < 2^{20}$。 - 每个询问中 $0 \le U, V < N$。 ### 子任务 1. （$5$ 分） $N \le 10$。 2. （$9$ 分）对于所有 $0 \le i < N$， $W[i] \le 1$。 3. （$15$ 分） $N \le 200$。 4. （$28$ 分）对于所有 $0 \le i < N$， $W[i] < 128$。 5. （$28$ 分） $N \le 10\ 000$。 6. （$15$ 分）没有额外约束。