**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.