# TREEXOR-Editorial

Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

2262

# 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 y=0;
if(vi[j])continue;
vi[j]=true;
}
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;
for(int i=0;i<n-1;i++){
int t;
cin >> t;
}
done=k;
vector<char>ans(n+1,'0');
vector<bool>vi(n+1,false);
vi[1]=true;
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;
{
if(child != par)
{
//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;
vec.resize(n+1);
for(int i=2; i<=n; i++){
int x;
std::cin >> x;
}
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

Can any tell me why my sol is giving WA ?