Accurate XOR Codechef problem Solution CoderCEO

Accurate XOR Codechef Problem Solution ( TREEXOR )

Chef has a tree consisting of $N$ nodes, rooted at node $1$ . The parent of the $i^{t h} (2 \leq i \leq N)$ node in the tree is the node $P_{i}$ .

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 $N$ nodes in the tree is exactly $K$ .

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 $T$ , denoting the number of test cases.
The first line of each test case contains two space-separated integers $N$ and $K$ , denoting the number of vertices in the tree and the required sum of Xor-value respectively.
The second line of each test case contains $N - 1$ space-separated integers $P_{2}, P_{3}, \dots, P_{N}$ , where $P_{i}$ denotes the parent-node of the $i^{t h}$ node.

Output Format

For each test case, print on a new line a binary string of length $N$ where the $i^{t h} (1 \leq i \leq N)$ character of the string denotes the binary value assigned to node $i$ . If there are multiple ways to assign values to the node, you can do it in any way.

Constraints

$1 \leq T \leq 10^{5}$
$2 \leq N \leq 2 \cdot 10^{5}$
$0 \leq K \leq N$
$1 \leq P_{i} < i$ for each $2 \leq i \leq N$
The sum of $N$ over all test cases won’t exceed $2 \cdot 10^{5}$ .

Sample Input 1

Sample Output 1

00
100
11010

Explanation

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

Test case $2$ : The Xor-value of the node $1$ is $1$ and the remaining nodes have Xor-value $0$

Test case $3$ : The Xor-value of the nodes $1, 4$ is $1$ and the remaining nodes have Xor-value $0$ .

				
					using namespace std;
int done;
int dfs(vector<vector<int>>&adj,int x,vector<char>&ans,vector<bool>&vi){
    int y=0;
    for(auto j:adj[x]){
        if(vi[j])continue;
        vi[j]=true;
        y+=dfs(adj,j,ans,vi);
    }
    if(done){
        ans[x]='0'+1-(y%2);
        done--;
        return 1;
    }
    ans[x]='0'+(y%2);
    return 0;
}
int main() {
	int T;
	cin >> T;
	while(T--){
	    int n,k;
	    cin >> n >> k;
	    vector<vector<int>>adj(n+1);
	    for(int i=0;i<n-1;i++){
	        int t;
	        cin >> t;
	        adj[i+2].push_back(t);
	        adj[t].push_back(i+2);
	    }
	    done=k;
	    vector<char>ans(n+1,'0');
	    vector<bool>vi(n+1,false);
	    vi[1]=true;
	    int m=dfs(adj,1,ans,vi);
	    for(int i=1;i<=n;i++)cout << ans[i];
	    cout << endl;
	}
	return 0;
}

Accurate XOR Codechef problem Solution

Published by Govind Deshmukh on July 20, 2022July 20, 2022