P14964 [LBA-OI R2 C] 可比豆出道计划

可比豆：你长得很像 cn（我们班主任） 后撤步：（跳脚） 众人：（摇头）一点都不像 可比豆：（跳脚） **本题时空限制均为 std 的 3 倍以上。** **为方便阅读，我们提供了形式化题意。**

在 LBA 的璀璨星空中，可比豆是最耀眼的那颗星。无数小迷妹为他痴狂，有 $k$ 个小迷妹自发组成了 $n$ 个应援团体。 这些小团体宛如一棵参天大树：每个小迷妹是一片独立的叶子，而她们又聚合成更大的枝干，最终汇聚成那最粗壮的树干——可比豆全球后援会。 这棵由小迷妹们组成的树有 $n$ 个节点，根节点是"可比豆全球后援会"（编号为 $1$）。每个叶子节点代表一个小迷妹，她有一个初始的号召力值 $w_i \in [1, n]$。 非叶子节点的号召力则由其直接子节点的号召力决定——取它们的中位数。具体来说，如果一个节点有 $s$ 个子节点，将它们的号召力从小到大排序后，取第 $\lceil \frac{s}{2} \rceil$ 个值作为该节点的号召力。 现在，小迷妹们迎来了千载难逢的机会：她们有 $m$ 次与可比豆见面的机会！每次见面可以让任意一个小迷妹（即任意一个叶子节点，允许重复选择）的号召力变为 $[1, n]$ 中的任意整数。 作为小迷妹中最聪明的你，需要制定最优的见面安排方案，让"可比豆全球后援会"（根节点）的号召力达到最大，以备不时之需，你需要对 $m\in[0,k]$ 求出答案。 #### 形式化题意 给定一棵 $n$ 个点，$k$ 个叶子的根为 $1$ 的树，给定叶子结点的权值，值域为 $[1,n]$，非叶子结点的权值为其子节点的权值的中位数。 现在可以进行 $m$ 次操作，每次操作选择一个叶子节点（允许重复选同一个叶子），将其权值改为 $[1,n]$ 中的任意整数。 求最大化根节点权值，你需要对 $m\in [0,k]$ 求出答案。 长度为 $n$ 的序列的中位数定义为将序列从小到大排序后第 $\lceil \frac{n}{2}\rceil$ 的数。

第一行两个整数 $n,k$，含义如题所述。 第二行 $n$ 个整数，对于第 $i$ 个数 $w_i$， - 若 $w_i=0$，表示编号为 $i$ 的节点是非叶子节点。 - 若 $w_i\ne 0$，表示编号为 $i$ 的点是叶子结点，其权值为 $w_i$。 第三行 $n-1$ 个整数，第 $i$ 个整数 $fa_{i+1}$ 表示 $i+1$ 的父亲。 **特别地，根节点不是叶子节点，保证 $w_1=0$。**

记 $ans_i$ 为 $m=i$ 时的答案，你需要输出一行，一个整数，表示 $\bigoplus\limits_{i=0}^k(i\times ans_i)$ 的结果，其中 $\oplus$ 表示按位异或。

#### 样例解释 1 - 对于 $m=0$，此时 $1$ 号点的权值为序列 $\{1,2,3,4\}$ 的中位数为 $2$。 - 对于 $m=1$，一种最优策略是将 $2$ 号点的权值改为 $3$，此时 $1$ 号点的权值为序列 $\{2,3,3,4\}$ 的中位数为 $3$。 - 对于 $m=2$，一种最优策略是将 $2,3$ 号点的权值改为 $4$，此时 $1$ 号点的权值为序列 $\{3,4,4,4\}$ 的中位数为 $4$。 - 对于 $m=3,4$，$1$ 号点的权值为 $5$。 因此答案为 $0\times 2 \oplus 1\times 3\oplus 2\times 4 \oplus 3\times5 \oplus 4\times5=16$。 #### 样例解释 2 对于 $m\in[0,6]$，答案分别为 $3,3,4,10,10,10,10$。 ### 数据范围 | 子任务编号 | 数据范围 | 特殊限制 | 分值 | |:-:|:-:|:-:|:-:| | $1$ | $n,k\le 20$ | 无 | $10$ | | $2$ | $n,k\le 300$ | 无 | $10$ | | $3$ | $n\le 2\times 10^3$ | 无 | $10$ | | $4$ | $n\le 7\times 10^3$ | 无 | $10$ | | $5$ | $n\le 10^5$ | 无 | $15$ | | $6$ | $n\le 4\times 10^5$ | 无 | $15$ | | $7$ | 无特殊限制 | 无 | $30$ | 对于 $100\%$ 的数据：$1\le k