P17636 [ICPC 2019 Yinchuan R] XOR Tree

给定一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$，根为节点 $1$。每个节点有一个给定的权值 $a_i$。 我们定义 $d(x, y)$ 为从节点 $x$ 到节点 $y$ 的最短路径上的边数，并定义多重集 $p(x, k)$ 为 $\{a_y \mid y \text{ 在 } x \text{ 的子树中且 } d(x, y) \leq k\}$。注意这里 $a_x \in p(x, k)$。 我们定义任意集合的 **得分** 为其中任意两个数的异或值的平方之和。例如，集合 $\{1, 1, 2, 3\}$ 的得分应为 $$ (1 \oplus 1)^2 + (1 \oplus 2)^2 + (1 \oplus 3)^2 + (1 \oplus 2)^2 + (1 \oplus 3)^2 + (2 \oplus 3)^2 = 27 $$ 其中 $\oplus$ 表示按位异或运算。 现在给定参数 $k$。对于每个节点 $x$，你需要计算 $p(x, k)$ 的得分。

第一行输入包含两个整数 $n, k~(1 \leq k \leq n \leq 100000)$，分别表示树的节点数和上述参数。 第二行输入包含 $n$ 个整数，第 $i$ 个数 $a_i~(1 \leq a_i \leq 10^9)$ 是第 $i$ 个节点的权值。 第三行输入包含 $n-1$ 个整数，第 $i$ 个数 $f_{i+1}~(1 \leq f_{i+1} \leq i)$ 是第 $(i+1)$ 个节点的父节点。

输出 $n$ 行，第 $i$ 行包含一个整数，即 $p(i, k)$ 的得分。注意答案可能极其巨大，请改为输出其对 $2^{64}$ 取模的结果。

翻译由 DeepSeek V4 Pro 完成