TREEXOR-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

DIFFICULTY:

2262

PREREQUISITES:

Bit Manipulation, Graph Traversal (DFS)

PROBLEM:

Chef has a tree consisting of N nodes, rooted at node 1. The parent of the i^{th}\;(2\le i \le 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.

EXPLANATION:

Hint

You can choose any K nodes to have Xor-value 1 and other N - K nodes to have Xor-value 0.
We know that the Xor-value of any node is the Xor of all the Xor-values of its children and the value of the current node.

Xor-value of node = Value of node \oplus Xor of Xor-values of all children

This is because, for any node, irrespective of the Xor-values of its children we can always assign 0 or 1 to the current node so that Xor-value of the current node is of our choice.

Value of node = Chosen Xor-value of node \oplus Xor of Xor-values of all children

Solution

Let us use the standard DFS graph traversal algorithm and choose the K nodes having Xor-value 1 to be the K nodes having the least Post-visit numbers i.e. the time at which the DFS call for a node finishes.

By using DFS it is clear that when we are at a point to decide the value of a node, all the values of the nodes in its subtree are already decided. We also know the Xor-values of all its children and using this information we can always make the Xor-value of the current node of our choice.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
using namespace std;
const int N = 2e5 + 10;

int n, k, sum[N];
vector<int> g[N];

string ans;

void dfs(int v) {
	for (auto u : g[v]) {
		dfs(u);
		sum[v] += sum[u];
	}
	if (k) {
		if (sum[v] % 2 == 0) {
			ans[v] = '1';
			sum[v]++;
		}
		k--;
	} else {
		if (sum[v] % 2) {
			ans[v] = '1';
			sum[v]++;
		}
	}
}
int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> k;
		ans.clear();
		for (int i = 0; i < n; i++) {
			g[i].clear();
			sum[i] = 0;
			ans.push_back('0');
		}
		for (int i = 1; i < n; i++) {
			int x;
			cin >> x;
			g[x - 1].push_back(i);
		}
		dfs(0);
		cout << ans << '\n';
	}
	return 0;
}

Editorialist's Solution
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;
}
2 Likes

Shouldn’t the xor-value of node just be the xor of xor-value of all children? I am really confused, link you’ve provided for the subtree say “Subtree: The tree which is a child of a node.”

2 Likes

Subtree of a node includes all the descendants of that node + that node.
https://science.jrank.org/programming/Tree_Structures.html

1 Like

This is the link that was provided in the question. This clearly say children of the node .

1 Like

Can someone please find a test case where my code doesn’t work ?? Or any changes I should make??

#include <bits/stdc++.h>
#define int long long int

std::vector <int> vec;
int k;
void fun(int src, int par, std::vector<int>& ans, std::vector <int> adj[])
{
    int subords = 0;
    for(int child : adj[src])
    {
        if(child != par)
        {
            fun(child, src, ans, adj);
            //std::cout << ans[child] << " " << child << " " << src << " " << k << "\n";
            if(k > 0){
                if(ans[child]%2 == 0)
                    vec[child] = 1;
                k -= 1;
            }
            else{
                if(ans[child]%2)
                    vec[child] = 1;
            }
            subords += (vec[child]);
        }
    }
    //std::cout << src << " " << subords << "\n";
    ans[src] = subords;
}

void solve(){
    k = 0;
    vec.clear();
    int n;
    std::cin >> n >> k;
    std::vector <int> adj[n+1], ans(n+1);
    vec.resize(n+1);
    for(int i=2; i<=n; i++){
        int x;
        std::cin >> x;
        adj[i].push_back(x);
        adj[x].push_back(i);
    }
    fun(1, 0, ans, adj);
    if(k){
        if(ans[1]%2 == 0)
            vec[1] = 1;
    }
    else{
        if(ans[1]%2)
            vec[1] = 1;
    }
    for(int i=1; i<=n; i++)
        std::cout << vec[i];
    std::cout << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

The definition of Subtree is well known. But the links provided in the question don’t seem to reflect what the editorialist considers a subtree. A more engaging definition should’ve been provided.

2 Likes

https://www.codechef.com/viewsolution/69503770

Can any tell me why my sol is giving WA ?
sol link-CodeChef: Practical coding for everyone
My idea;- I am traversing from the last level to the 1st level and if k>0 then making the node val 0 1 accordingly.for next level i am also maintaining the xor of its children

why my solution is not working . can someone help?
https://www.codechef.com/viewsolution/69506755

My approch is similar to yours but my code is givng WA can you help why?
https://www.codechef.com/viewsolution/69506755

What is wrong with this solution?

First of all why confuse the definition of subtree. Even so, atleast could have provided the definition along with question rather than a separate link, since it was different than usual. Adding to that, the sample case works fine for both definitions.