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.

last update: