G. Centroid Guess
interactive; probabilities; trees
This in an interactive problem.There is an unknown tree consisting of \(n\) nodes, which has exactly one centroid. You only know \(n\) at first, and your task is to find the centroid of the tree.You can ask the distance between any two vertices for at most \(2\cdot10^5\) times. Note that the interactor is not adaptive. That is, the tree is fixed in each test beforehand and does not depend on your queries.A vertex is called a centroid if its removal splits the tree into subtrees with at most \(\lfloor\frac{n}{2}\rfloor\) vertices each.
The only line of the input contains an integer \(n\) (\(3\le n\le 7.5\cdot10^4\)) — the number of nodes in the tree.
Here is an image of the tree from the sample.