CF 2193G - Paths in a Tree

We are given a tree, which is an undirected, connected, acyclic graph of $n$ vertices. Two hidden vertices, $x$ and $y$, define a unique path because trees have exactly one simple path between any pair of vertices.

codeforcescompetitive-programmingdfs-and-similarinteractivesortingstrees

CF 2193G - Paths in a Tree

Rating: 2100
Tags: dfs and similar, interactive, sortings, trees
Solve time: 3m 5s
Verified: no

Solution

Problem Understanding

We are given a tree, which is an undirected, connected, acyclic graph of $n$ vertices. Two hidden vertices, $x$ and $y$, define a unique path because trees have exactly one simple path between any pair of vertices. We do not know the identities of $x$ and $y$, but we can interact with the tree by asking whether the path between any two chosen vertices $a$ and $b$ intersects the hidden path between $x$ and $y$. Our goal is to find at least one vertex on the hidden path using at most