 # LCAINTERACT - Editorial

Author: Ray Bai
Developer: Roman Bilyi
Editorialist: Anton Trygub

# DIFFICULTY:

3145

There are many different approaches that achieve various bounds. We will describe the solutions which work for n = 500 in 10 queries, and in 9 queries.

10 queries: Suppose that r is the root. First, let’s ask a query about all leaves. Their LCA has to be r (if r is a leaf, it’s clear; otherwise, there is a leaf in each of the subtrees of r). So, we can determine if r is a leaf with this query.

Now if r is not a leaf, let’s ask queries for sets, which contain all leaves. We will get `YES` iff we have included r into the set. So, we can do binary search on the non-leaf nodes, discarding roughly half at each time. This way, we will need at most 9 queries.

Suppose now that r is a leaf. If we ask a question about some subset of the leaves of size \ge 2, the answer will be `YES` if and only if r is in the chosen set. So, we can once again do binary search on the leaves, until we get at most 2 candidates r_1, r_2. At that point, we can ask a query for nodes r_2, r_3, where r_3 is any other leaf, to determine if r_2 is the root. This way, we will also need at most 9 queries.

Adding the initial query about all leaves, we are done in 10 queries.

9 queries: Our algorithm loses one query at the first step: it might be the case that the number of remaining candidates is n - some small number (when the root is a leaf, and almost all nodes are leaves, for example). Let’s try to solve this issue.

Let’s arrange our nodes in the following fashion: first all leaves, then all non-leaves. What happens if we ask a query about the some prefix of this order of length at least 2? Let’s consider two cases.

• Our prefix contains all the leaves, and, maybe, some other nodes. Then their LCA is r, and we will get `YES` if and only if r is in that prefix.

• Our prefix is some subset of the leaves. Then, if r is among them, we will get`YES`, otherwise their LCA would be some node different from any of them, so we will get `NO`. Once again, we will get `YES` if and only if r is in that prefix.

So, we can do binary search on this order of nodes! The only exception is when we end up with a prefix of length 2. Then, as in previous subtask, we should ask one of these leaves with one of other leaves.

This solves the problem in 9 queries.