# INTREENCLR - Editorial

Setter: Jay Sharma
Tester: Nishank Suresh
Editorialist: Taranpreet Singh

Easy-Medium

Observation, DFS

# PROBLEM

You are given a tree having N nodes. Each node of this tree is colored either Black or White but you don’t know the initial color of any node.

You can ask up to Q queries. In each query, you will give a node to the grader. The grader will flip the color of this node and then return the number of edges in the tree connecting nodes of different colors. Note that the flipping of color is permanent, meaning that the color of the node remains flipped after the query.

Your task is to make the color of all nodes the same.

# QUICK EXPLANATION

• Root the tree at any node, and for each node, attempt to find out whether it has the same color as its parent node or not.
• Let’s assume we have already calculated this information for all children of the current node, and we aim to compute it for the current node.
• Make a query at the current node. Assuming the answer to the previous query was P and the answer to the current query is Q, and there are A children with the same color as the current node, and B nodes with the opposite color as the current node, then we can calculate w = (Q-P+A-B+1)/2, and determine if it has the same color as its parent or not, by checking if w = 0 or w = 1.
• After computing this information, one of the colors must have up to \left\lfloor \frac{N}{2} \right\rfloor nodes with that color. We can compute this via DFS, and flip the color of those nodes.

# EXPLANATION

First of all, since there’s no way to identify the actual color or node by any query, we shall assume the color of one node, and determine the color with respect to the color of that node.

Let’s assume node 1 is the root and is colored white. Apart from node 1, we need to determine whether node u as same or opposite color as the parent of node u. Let’s denote parent of node u as P_u. Also, denote S_u = 0 if node u has same color as it’s parent, otherwise S_u = 1.

### Computing S_u for leaf nodes u

Let’s try computing S_u for leaf node u. If we consider the answer to the previous and current queries, the only pairs changed are related to node u. Let’s assume P denotes the answer to the previous query, and C is the answer to the current query after the color of node u is flipped. Only two situations are possible.

• C = P+1: In this case, a new pair with opposite colors got created, which means, currently, node u has opposite color as node P_u, which implies S_u = 1.
• C = P-1: In this case, an existing pair with opposite colors got removed, which means, currently, node u has same color as node P_u, which implies S_u = 0.

### Computing S_u for non-leaf nodes u

Generalizing the above approach, now we also need to consider children of node u as well. Let’s assume we are computing it in a bottom-up manner, where S_v is already computed for all children of node u.

When we make a query for node u, S_v gets flipped for all immediate children v of node u, as the color of u got changed. We need to maintain S_u for current colors.

Let’s say we have made a query for node u, and C is the response to a query to the current query and P is a response to the previous query.

Let’s assume there are a children of u with the same color and b nodes with opposite color after the flipping color of the current node.

Let’s assume D denotes the number of pairs of opposite-colored nodes, with no endpoint in pair being node u.

P = D + (1-S_u) + a
C = D + S_u + b

Subtracting these, we can obtain S_u = (C - P + a - b +1)/2. This is enough to determine whether node u has same or opposite color as P_u using just 1 query.

It took N-1 queries for each non-root nodes, but we also need number of pairs before first query, so, we need to make 1 additional query. Hence, we used up exactly N queries and we know for each node whether it has same color as its parent or not.

By running a DFS, we can determine color of each node wrt color root node. One of the color is guaranteed to have \leq N/2 nodes of that color, so once we find colors, we can flip colors of those nodes, taking at most N/2 operations.

Hence, we took at most 3*N/2 operations.

# TIME COMPLEXITY

The time complexity is O(N) per test case.

# SOLUTIONS

Setter's Solution
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

#include <bits/stdc++.h>
using namespace std;

{
{
if(v!=parent[u])
{
parent[v]=u;
}
}
}

void dfs2(vector<int> adj[],int parent[],int diff[],int u,int &prev)
{
int x=0,y=0;
{
if(v!=parent[u])
{
if(diff[v])
y++;
else
x++;
}
}
if(u!=0)
{
cout << u+1 << endl;
int next;
cin >> next;
int w=(prev-next+x-y+1)/2;
diff[u]=1-w;
{
if(v!=parent[u])
diff[v]=1-diff[v];
}
prev=next;
}
}

void dfs3(vector<int> adj[],int parent[],int diff[],int c[],int u)
{
{
if(v!=parent[u])
{
c[v]=c[u]^diff[v];
}
}
}

int main()
{
int tc=1;
cin >> tc;
while(tc--)
{
int n,q;
cin >> n >> q;
int parent[n];
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
u--,v--;
}
parent[0]=0;
int diff[n];
cout << 1 << endl;
int prev;
cin >> prev;
int c[n];
c[0]=1;
int white=0,black=0;
for(int i=0;i<n;i++)
{
if(c[i]==1)
white++;
else
black++;
}
int less;
if(black<white)
less=0;
else
less=1;
for(int i=0;i<n;i++)
{
if(c[i]==less)
{
cout << i+1 << endl;
int v;
cin >> v;
}
}
cout << 0 << endl;
int result;
cin >> result;
assert(result==1);
}
return 0;
}

Tester's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
ios::sync_with_stdio(0); cin.tie(0);

auto solve = [&] () {
int n, q; cin >> n >> q;
vector<vector<int>> tree(n+1);

for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}

auto query = [&] (int u) {
cout << u << endl;
int res; cin >> res;
if (res == -1) exit(0);
return res;
};

int ans = query(1), samect = 0;
vector<int> change(n+1), col(n+1);
auto dfs = [&] (const auto &self, int u, int p) -> int {
int diff = 0, children = 0;
for (int v : tree[u]) {
if (v == p) continue;
int add = self(self, v, u);

++children;
}

if (u == 1) return 0;
int cur = query(u);
for (int v : tree[u]) {
if (v != p)
change[v] ^= 1;
}

int x = (ans + children - 2*diff + 1 - cur)/2;
ans = cur;
return change[u] = 1 - x;
};
auto dfs2 = [&] (const auto &self, int u, int p) -> void {
samect += col[u] == 0;
for (int v : tree[u]) {
if (v == p) continue;
col[v] = change[v] ^ col[u];
self(self, v, u);
}
};
dfs(dfs, 1, 0);
dfs2(dfs2, 1, 0);

int which = samect > n - samect;
for (int i = 1; i <= n; ++i) {
if (col[i] == which)
query(i);
}
query(0);
};

int t; cin >> t;
for (int test = 1; test <= t; ++test) {
solve();
}
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class INTREENCLR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), Q = ni();
int[] from = new int[N-1], to = new int[N-1];
for(int i = 0; i< N-1; i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] tree = tree(N, from, to);
boolean[] same = new boolean[N];
//same[i] denotes whether node i has same color as its parent or not
query(0);
dfs(tree, same, 0, -1);

int[] col = new int[N];
color(tree, col, same, 0, -1);
int[] cnt = new int[2];
for(int i = 0; i< N; i++)cnt[col[i]]++;
int flip = cnt[0] < cnt[1]?0:1;
for(int i = 0; i< N; i++)if(col[i] == flip)query(i);
pni(0);
hold(ni() == 1);
}
void color(int[][] tree, int[] col, boolean[] same, int u, int p){
for(int v:tree[u]){
if(v == p)continue;
col[v] = same[v]?col[u]:(1-col[u]);
color(tree, col, same, v, u);
}
}
long prevQuery = -1, curQuery = -1;
void dfs(int[][] tree, boolean[] sameColor, int u, int p) throws Exception{
for(int v:tree[u])if(v != p)dfs(tree, sameColor, v, u);
if(p == -1)return;
query(u);
int same = 0, diff = 0;
for(int v:tree[u]){
if(v == p)continue;
sameColor[v] = !sameColor[v];
// Since after query on u, color of u is flipped
if(sameColor[v])same++;
else diff++;
}

long w = (curQuery - prevQuery + same - diff +1)/2;
sameColor[u] = w == 0;
}
void query(int u) throws Exception{
pni(1+u);
prevQuery = curQuery;
curQuery = nl();
hold(curQuery != -1);
}
//creates adjacency list representation using jagged arrays in java, faster than array of lists
int[][] tree(int N, int[] from, int[] to){
int[][] g = new int[N][];
int[] c = new int[N];
for(int x:from)c[x]++;
for(int x:to)c[x]++;
for(int i = 0; i< N; i++)g[i] = new int[c[i]];
for(int i = 0; i< N-1; i++){
g[from[i]][--c[from[i]]] = to[i];
g[to[i]][--c[to[i]]] = from[i];
}
return g;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new INTREENCLR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

5 Likes

I request the editorialist to share the approaches for 12,20,20 points too

Here are the intended solutions for the subtasks. You can find other solutions from participants’ submissions.

Assign random colors to all leaf nodes and move from leaves to the root. We will try to maintain the color of all nodes in a subtree the same. Suppose we know that a particular subtree has all nodes of the same color. Let’s query the root node of this subtree. Let its degree be D. There are two possible cases -

• The answer increases by D. It is possible if the parent of the queried node had the same color as the queried node. In such a case, we will query this node again to maintain the unicolor subtree property.
• The answer increases by the D-2. It is possible if the parent of the queried node had different color as the queried node. In such a case, we will query all nodes in the subtree of this node except the node itself.

Total number of queries used will be at most N^2.

Without loss of generality, let us assume we already know that a node is black. Suppose it has degree D and the answers before querying this node was P and after querying this node is Q. Let B be the number of black neighbours, W be the number of white neighbours and Z be the number of edges connecting nodes of different colors not having an endpoint as this node. Then,

P=W+Z
Q=B+Z
D=B+W

Solving this system of equations, we get B=\dfrac{D+Q-P}{2} and W=\dfrac{D+P-Q}{2}. So, querying a node can tell us how many neighbours of this node are black and how many are white.

Suppose we already know whether a node is black or white and how many neighbours of this node are black and white respectively. Now, we will query any one of its children and then this node again. Let’s calculate the new values of number of white and black neighbours of this node. Clearly, any change in this value will be due to the child that we queried and by seeing whether the number of white neighbours decreased or the number of black neighbours decreased, we can determine the color of the child node we queried.

After we know the colors of all nodes, we can pick any color and query all nodes of that color to make the tree unicolor. It is not hard to see that determining the colors requires at most 2N queries and flipping of colors requires at most N queries, making a total of 3N queries.

This is basically the same as the intended solution given in the editorial except that for the last part, instead of choosing the color with lesser number of nodes, we can choose any color and flip all the nodes of this color, making the total number of queries used at most 2N.

## Solutions

/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

#include <bits/stdc++.h>
using namespace std;

{
{
if(v!=parent[u])
{
parent[v]=u;
}
}
}

void reverse(vector<int> adj[],int parent[],int u,int &prev)
{
{
if(v!=parent[u])
{
cout << v+1 << endl;
cin >> prev;
}
}
}

void dfs2(vector<int> adj[],int parent[],int u,int &prev)
{
{
if(v!=parent[u])
}
{
if(v!=parent[u])
{
int x;
cout << v+1 << endl;
cin >> x;
{
cout << v+1 << endl;
cin >> x;
}
else
{
prev=x;
}
}
}
}

int main()
{
int tc=1;
cin >> tc;
while(tc--)
{
int n,q;
cin >> n >> q;
int parent[n];
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
u--,v--;
}
parent[0]=0;
cout << 1 << endl;
int prev;
cin >> prev;
cout << 0 << endl;
int result;
cin >> result;
assert(result==1);
}
return 0;
}

/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

#include <bits/stdc++.h>
using namespace std;

{
{
if(v!=parent[u])
{
parent[v]=u;
}
}
}

void dfs2(vector<int> adj[],int parent[],int black[],int white[],int c[],int u,int &prev)
{
{
if(v!=parent[u])
{
int b=black[u];
int x,y;
cout << v+1 << endl;
cin >> x;
cout << u+1 << endl;
cin >> y;
c[u]=1-c[u];
if(c[u]==1 && u>0)
{
black[parent[u]]--;
white[parent[u]]++;
}
else
{
black[parent[u]]++;
white[parent[u]]--;
}
if(c[u]==0)
{
}
else
{
}
if(u>0 && c[parent[u]]==0)
black[u]--;
else if(u>0)
white[u]--;
if(black[u]<b)
{
c[v]=1;
if(c[u]==1)
black[v]--;
else
white[v]--;
}
else
{
c[v]=0;
if(c[u]==1)
black[v]--;
else
white[v]--;
}
b=black[u];
prev=y;
}
}
}

int main()
{
int tc=1;
cin >> tc;
while(tc--)
{
int n,q;
cin >> n >> q;
int parent[n];
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
u--,v--;
}
if(n==2)
{
int v;
cout << 1 << endl;
cin >> v;
if(v==1)
{
cout << 1 << endl;
cin >> v;
}
cout << 0 << endl;
int result;
cin >> result;
assert(result==1);
continue;
}
parent[0]=0;
int x,y;
cout << 1 << endl;
cin >> x;
cout << 1 << endl;
cin >> y;
int black[n],white[n],c[n];
memset(black,-1,sizeof(black));
memset(white,-1,sizeof(white));
memset(c,-1,sizeof(c));
c[0]=0;
for(int i=0;i<n;i++)
{
if(c[i]==0)
{
cout << i+1 << endl;
int v;
cin >> v;
}
}
cout << 0 << endl;
int result;
cin >> result;
assert(result==1);
}
return 0;
}

/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

#include <bits/stdc++.h>
using namespace std;

{
{
if(v!=parent[u])
{
parent[v]=u;
}
}
}

void dfs2(vector<int> adj[],int parent[],int diff[],int u,int &prev)
{
int x=0,y=0;
{
if(v!=parent[u])
{
if(diff[v])
y++;
else
x++;
}
}
if(u!=0)
{
cout << u+1 << endl;
int next;
cin >> next;
int w=(prev-next+x-y+1)/2;
diff[u]=1-w;
{
if(v!=parent[u])
diff[v]=1-diff[v];
}
prev=next;
}
}

void dfs3(vector<int> adj[],int parent[],int diff[],int c[],int u)
{
{
if(v!=parent[u])
{
c[v]=c[u]^diff[v];
}
}
}

int main()
{
int tc=1;
cin >> tc;
while(tc--)
{
int n,q;
cin >> n >> q;
int parent[n];
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
u--,v--;
}
parent[0]=0;
int diff[n];
cout << 1 << endl;
int prev;
cin >> prev;
int c[n];
c[0]=1;
for(int i=0;i<n;i++)
{
if(c[i]==0)
{
cout << i+1 << endl;
int v;
cin >> v;
}
}
cout << 0 << endl;
int result;
cin >> result;
assert(result==1);
}
return 0;
}

1 Like

As we go from bottom to top, and if we are at u , then after determining S_{u} , we should flip all S_{v} where v is a child of u right? But, won’t that make it O(n^{2})?

No, it will be \mathcal{O}(n) because the sum of the number of children over all nodes in a tree is equal to N-1 (Every node except the root is a child of 1 node).

1 Like

Submission
I wrote the same code given in the video so that I could debug and understand. But, when I submitted the code I am getting W.A. Could someone please tell me where did I go wrong

Can anybody tell a testcase at which this code will fail, Or the mistake in the code, Please??
https://www.codechef.com/viewsolution/55523459

1. In the dfs function, if(it==parent) you should continue instead of return.
2. You forgot to take Q in the input.

Modified Code

1 Like

How is the color of a node equal to curr-same? That assumption is wrong.

Thank you soo much!

When we are making the query on the node first time, the output we will get is total number of same nodes in children + (if parent is different), so when i get total number of same nodes from children after doing dfs on its subtree, I remove it from the query to get 0 or 1, which determines whether it is same as it parent or not.
if you have any testcase for this to prove my assumption wrong, it would be a great help.

The value curr that you are getting is not just the number of different colored neighbours of the current node but the number of edges connecting different colored nodes in the whole tree (including edges not involving the current node). How are you taking them into account?

1 Like

Got my mistake, thanx a lot. I misunderstood it.

What is implied by the “previous” and “current” query? On which nodes are these respective queries made? There is no clear explanation to that in your editorial.