33OJ
登录 注册

#P17636. [ICPC 2019 Yinchuan R] XOR Tree

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

[ICPC 2019 Yinchuan R] XOR Tree

Problem Description

You are given a tree with nn nodes labelled from 11 to nn, the root of which is the node 11. Each node has a given value aia_i.

We define d(x,y)d(x, y) as the number of edges in the shortest path from the node xx to the node yy, and define a multiset p(x,k)p(x, k) as $\{a_y \mid y \text{ is in the subtree of } x \text{ and } d(x, y) \leq k\}$. Note that here ax∈p(x,k)a_x \in p(x, k).

We define the score of any arbitrary set as the sum of squares of XORs of any two numbers. For example, the score of the set {1,1,2,3}\{1, 1, 2, 3\} should be

$$(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$$

where ⊕\oplus denotes the bitwise exclusive-or.

Now you are given the parameter kk. For each node xx you need to compute the score of p(x,k)p(x, k).

Input Format

The first line of input contains two integers n,k (1≤k≤n≤100000)n, k~(1 \leq k \leq n \leq 100000), the number of nodes of the tree and the parameter described above.

The second line of input contains nn integers, the ii-th number ai (1≤ai≤109)a_i~(1 \leq a_i \leq 10^9) is the value of the ii-th node.

The third line of input contains n−1n-1 integers, the ii-th number fi+1 (1≤fi+1≤i)f_{i+1}~(1 \leq f_{i+1} \leq i) is the parent of the (i+1)(i+1)-th node.

Output Format

Output nn lines, the ii-th line contains a single integer, the score of p(i,k)p(i, k). Note that the answer can be extremely large, please output it modulo 2642^{64} instead.

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