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;
}