PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Farhod Farmon
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Centroid decomposition
PROBLEM:
You’re given a tree with N vertices, each vertex having assigned value a_i. We call v a bad adjacent of u if u and v are adjacent and a_v > a_u. You may ask at most 20 queries asking for number of some particular bad adjacent for given vertex v, you have to find a vertex without bad adjacents.
EXPLANATION:
As you may guess (and as often the case in problems like this), such vertex always exist, for example it’s the vertex with maximum possible a_i. But surely finding vertex with maximum a_i isn’t possible in under 20 queries for N>20.
To understand what we should do let’s consider case when we only have an array of values a_1, \dots, a_N instead of a tree, thus the tree is actually a bamboo. Problem here is pretty well-known and is solvable with binary search. Basically you just shrink current segment considering the direction you were given by the grader. It gives the answer in O(\log n), but what to do with trees?
There is another well-known trick for this called centroid decomposition. It may be proven that there is always a vertex (called centroid) such that if you delete it, all remaining subtrees will be at most half a size from initial tree. Thus if you always ask queries in centroid of current tree, you’ll also do everything in O(\log n) queries.
That’s the whole idea of the solution, everything other is technicalities. Common way to find centroid is to do it in two steps. On first steps you calculate sizes of all subtrees of current tree:
vector<vector<int>> g;
vector<int> size, block;
void dfs(int v, int p) {
size[v] = 1;
for(auto u: g[v]) {
if(u != p && !block[u]) {
dfs(u, v);
size[v] += size[u];
}
}
}
Then you make another go over the tree to find the centroid, going into too large subtrees:
int get(int v, int p, int n) {
for(auto u: g[v]) {
if(u != p && 2 * size[u] > n && !block[u]) {
return get(u, v, n);
}
}
return v;
}
Thus the whole function to find the centroid is as follows:
int find_centroid(int v, int p) {
fill(begin(size), end(size), 0);
dfs(v, p);
return get(v, p, size[v]);
}
Now that we may quickly find centroid, we can use the following code to deal with queries:
int v = find_centroid(0, 0);
while(true) {
int u = ask(v);
if(u != -1) {
block[v] = 1;
v = find_centroid(u, v);
} else {
break;
}
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.