#P17636. [ICPC 2019 Yinchuan R] XOR Tree
[ICPC 2019 Yinchuan R] XOR Tree
题目描述
给定一棵有 个节点的树,节点编号为 到 ,根为节点 。每个节点有一个给定的权值 。
我们定义 为从节点 到节点 的最短路径上的边数,并定义多重集 为 $\{a_y \mid y \text{ 在 } x \text{ 的子树中且 } d(x, y) \leq k\}$。注意这里 。
我们定义任意集合的 得分 为其中任意两个数的异或值的平方之和。例如,集合 的得分应为
$$(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$$其中 表示按位异或运算。
现在给定参数 。对于每个节点 ,你需要计算 的得分。
输入格式
第一行输入包含两个整数 ,分别表示树的节点数和上述参数。
第二行输入包含 个整数,第 个数 是第 个节点的权值。
第三行输入包含 个整数,第 个数 是第 个节点的父节点。
输出格式
输出 行,第 行包含一个整数,即 的得分。注意答案可能极其巨大,请改为输出其对 取模的结果。
6 1
4 3 2 4 3 1
1 1 2 2 5
86
98
0
0
4
0
提示
翻译由 DeepSeek V4 Pro 完成