MYS00T - Editorial


Contest, div. 1
Contest, div. 2

Author: Farhod Farmon
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov

Centroid decomposition
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.
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 {

Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.


Hi melfice,
Thanks for this quick and nice editorial, I am able to understand most of it except how travelling in the direction pointed by the judge will always give you the max ai. Can you please explain?

It is not. It will give a local max.

1 Like

My bad English. I am only now has understand that answer is index of bigger vertex, not number of adjacent vertexes that bigger.

I too assumed this first. But trying to sample test cases and rereading it made me realise that it returns index.