#P17636. [ICPC 2019 Yinchuan R] XOR Tree
[ICPC 2019 Yinchuan R] XOR Tree
Problem Description
You are given a tree with nodes labelled from to , the root of which is the node . Each node has a given value .
We define as the number of edges in the shortest path from the node to the node , and define a multiset as $\{a_y \mid y \text{ is in the subtree of } x \text{ and } d(x, y) \leq k\}$. Note that here .
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 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 denotes the bitwise exclusive-or.
Now you are given the parameter . For each node you need to compute the score of .
Input Format
The first line of input contains two integers , the number of nodes of the tree and the parameter described above.
The second line of input contains integers, the -th number is the value of the -th node.
The third line of input contains integers, the -th number is the parent of the -th node.
Output Format
Output lines, the -th line contains a single integer, the score of . Note that the answer can be extremely large, please output it modulo instead.
6 1
4 3 2 4 3 1
1 1 2 2 5
86
98
0
0
4
0