33OJ
登录 注册

#P17636. [ICPC 2019 Yinchuan R] XOR Tree

    ID: 20141 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>数学2019树链剖分前缀和ICPC

[ICPC 2019 Yinchuan R] XOR Tree

题目描述

给定一棵有 nn 个节点的树,节点编号为 11 到 nn,根为节点 11。每个节点有一个给定的权值 aia_i。

我们定义 d(x,y)d(x, y) 为从节点 xx 到节点 yy 的最短路径上的边数,并定义多重集 p(x,k)p(x, k) 为 $\{a_y \mid y \text{ 在 } x \text{ 的子树中且 } d(x, y) \leq k\}$。注意这里 ax∈p(x,k)a_x \in p(x, k)。

我们定义任意集合的 得分 为其中任意两个数的异或值的平方之和。例如,集合 {1,1,2,3}\{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 表示按位异或运算。

现在给定参数 kk。对于每个节点 xx,你需要计算 p(x,k)p(x, k) 的得分。

输入格式

第一行输入包含两个整数 n,k (1≤k≤n≤100000)n, k~(1 \leq k \leq n \leq 100000),分别表示树的节点数和上述参数。

第二行输入包含 nn 个整数,第 ii 个数 ai (1≤ai≤109)a_i~(1 \leq a_i \leq 10^9) 是第 ii 个节点的权值。

第三行输入包含 n−1n-1 个整数,第 ii 个数 fi+1 (1≤fi+1≤i)f_{i+1}~(1 \leq f_{i+1} \leq i) 是第 (i+1)(i+1) 个节点的父节点。

输出格式

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

6 1
4 3 2 4 3 1
1 1 2 2 5
86
98 
0
0
4
0

提示

翻译由 DeepSeek V4 Pro 完成