I have a tree on $n$ vertices. Your goal is to find the adjacency list for it.
$n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the other $n-1$ vertices (i.e. you input an integer $1\leq i \leq n$ and get $n-1$ integers $1\leq d \leq n-1$). The lengths are listed in the order consistent with the enumeration of the vertices.
What is the algorithm using as few queries as possible (without making any additional assumptions about the tree)?
After the first query you can bipartition of the tree by the parity of the shortest path so $\lceil \frac{n}{2} \rceil$ queries are always sufficient. An algorithm that keeps adapting after each query might do better.