[Solution] Accurate XOR solution codechef

Accurate XOR solution codechef – Chef has a tree consisting of NN nodes, rooted at node 11. The parent of the ith(2iN)ith(2≤i≤N) node in the tree is the node PiPi.

[Solution] Accurate XOR solution codechef

Chef wants to assign a binary value (0 or 1) to every node of the tree. The Xor-value of a node is defined as the bitwise XOR of all the binary values present in the subtree of that node.

Help Chef to assign values to the nodes of the tree in such a way that the sum of Xor-value of all the NN nodes in the tree is exactly KK.

It can be shown that such an assignment always exists. If there are multiple possible answers, you may print any of them.

Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• The first line of each test case contains two space-separated integers NN and KK, denoting the number of vertices in the tree and the required sum of Xor-value respectively.
• The second line of each test case contains N1N−1 space-separated integers P2,P3,,PNP2,P3,…,PN, where PiPi denotes the parent-node of the ithith node.

Output Format

For each test case, print on a new line a binary string of length NN where the ith(1iN)ith(1≤i≤N) character of the string denotes the binary value assigned to node ii. If there are multiple ways to assign values to the node, you can do it in any way.

[Solution] Accurate XOR solution codechef

• 1T1051≤T≤105
• 2N21052≤N≤2⋅105
• 0KN0≤K≤N
• 1Pi<i1≤Pi<i for each 2iN2≤i≤N
• The sum of NN over all test cases won’t exceed 21052⋅105.

Sample Input 1

3
2 0
1
3 1
1 1
5 2
1 2 2 1


[Solution] Accurate XOR solution codechef

00
100
11010


Explanation

Test case 11: The Xor-value of both nodes is 0.

Test case 22: The Xor-value of the node 11 is 11 and the remaining nodes have Xor-value 00.

Test case 33: The Xor-value of the nodes 1,41,4 is 11 and the remaining nodes have Xor-value 00.