Contest Duration: - (local time) (120 minutes) Back to Home

## C - Tree Queries Editorial by evima

Let $$D_i=d_{1,i}+d_{2,i}$$. We can find this value for $$i=3,\ldots,N$$ in $$2(N-2)=2N-4$$ questions.

In many cases, the minimum value among $$D_i$$ equals $$d_{1,2}$$. The only exception is when $$d_{1,2}=1$$ (no vertices between Vertices $$1,2$$), where the minimum among $$D_i$$ is $$3$$. At this point, we can know $$d_{1,2}$$ unless the minimum $$D_i$$ is $$3$$.

Let us try to determine whether $$d_{1,2}$$ is $$1$$ or $$3$$ when the minimum $$D_i$$ is $$3$$. If we assume $$d_{1,2}=3$$, there would be exactly two indices $$i$$ such that $$D_i=3$$, so we should have $$d_{1,2}=1$$ otherwise.
When there are indeed exactly two indices $$i$$ such that $$D_i=3$$, let us call them $$x$$ and $$y$$. If $$d_{1,2}=1$$, each of $$x$$ and $$y$$ would be adjacent to Vertex $$1$$ or Vertex $$2$$; if $$d_{1,2}=3$$, $$x$$ and $$y$$ would be adjacent. Therefore, if $$d_{x,y}$$ is $$2$$ or $$3$$, we should have $$d_{1,2}=1$$; if it is $$1$$, we should have $$d_{1,2}=3$$.

From the above, we can know $$d_{1,2}$$ in at most $$2N-3$$ questions.

posted:
last update: