P17851 「RiOI-(-2)」houran 和芒果 / [ROI 2026 Day1] 泰莫利亚的调查 加强版

感谢 @[EricWan](/user/377873) 提供的一组 hack 数据。

houran 找到了一棵芒果树。 芒果树可以视为一棵 $n$ 个节点的有根树，根为 $1$。第 $i$ 个点到其父亲 $f_i$ 的边上有一个价值为 $w_i$ 的芒果。houran 可以在树上进行若干次采摘。具体地，他可以进行以下操作： - 选一个点 $u$ 出发。 - 往父亲方向移动若干次，每移动一条边就收集这条边上的芒果。 不过，由于 houran 对芒果过敏，他不能重复经过任何一个**节点**，也即任意两个操作不能经过重复的点。 给定 $m$，你需要求出：若 houran 最多可以进行 $m$ 次操作，获得的芒果的价值总和最大是多少。

**本题的测试点包含有多组测试数据。** 但不同测试数据只是通过修改 $w_2,w_3,\cdots,w_n$ 得到，其他内容均保持不变，请参考以下格式。其中 $\oplus$ 代表异或运算符。 第一行一个正整数 $n$。 接下来一行 $n-1$ 个数 $f_{2\sim n}$。 接下来一行 $n-1$ 个数 $w'_{2\sim n}$。 接下来一行包含一个正整数 $T$，表示有 $T$ 组测试数据。 接下来共 $T$ 行，每行描述一组数据，包含 $5$ 个非负整数 $X_0,X_1,X_2,X_3,m$，该组数据的 $w_i=w'_i \oplus X_{i\bmod 4}$，其中 $2\leq i\leq n$。

对于每一组数据，请你输出相应的答案。

### 【样例 $1$ 解释】 对于第一组询问，一个可能的最优取法如下： - $5\to4\to3\to1$，获得 $2+1+3=6$ 的价值。 总价值为 $6$。 对于第二、三组询问，一个可能的最优取法如下： - $5\to4\to3$，获得 $2+1=3$ 的价值。 - $2\to1$，获得 $5$ 的价值。 总价值为 $8$。 ### 【样例 $2$】 见选手目录下的 `mango/mango2.in` 与 `mango/mango2.ans`。 该样例满足测试点 $1$ 的约束条件。 ### 【样例 $3$】 见选手目录下的 `mango/mango3.in` 与 `mango/mango3.ans`。 该样例满足测试点 $2$ 的约束条件。 ### 【样例 $4$】 见选手目录下的 `mango/mango4.in` 与 `mango/mango4.ans`。 该样例满足测试点 $5$ 的约束条件。 ### 【样例 $5$】 见选手目录下的 `mango/mango5.in` 与 `mango/mango5.ans`。 该样例满足测试点 $6,7$ 的约束条件。 ### 【样例 $6$】 见选手目录下的 `mango/mango6.in` 与 `mango/mango6.ans`。 该样例满足测试点 $9\sim12$ 的约束条件。 ### 【样例 $7$】 见选手目录下的 `mango/mango7.in` 与 `mango/mango7.ans`。 该样例满足测试点 $13\sim15$ 的约束条件。 ### 【样例 $8$】 见选手目录下的 `mango/mango8.in` 与 `mango/mango8.ans`。 该样例满足测试点 $22\sim25$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $1\le m\le n\le 2\times 10^5$； - $1\le f_i