For the first subtask, it suffices to query each pair of adjacent nodes in the tree. Observe that if both nodes lie on the path between the two roots, the query will return 1. Otherwise, it will return 0. After determining the edges on the path between the two roots, the roots will just be the two endpoints of this path.

Query complexity: ~N-1~

For the second subtask, we observe that the tree is a chain. The path induced by the two roots is now a continuous interval along this chain. Therefore, we can binary search for the endpoints of this interval. Suppose we fix one end of our query at one end of the chain. Then, we binary search with the other endpoint of our query interval. Suppose we initially queried the endpoints of the chain and it returns a value of ~d~. Then we will move the other endpoint depending on if the query returns a value of ~d~ or not. A value of ~d~ signifies the entire interval is contained within the query interval so the second endpoint can be moved closer to the first endpoint of the chain. After we determine one endpoint, we can perform the same procedure for the other endpoint as well.

Query complexity: ~2\log(N)+1~

For the third subtask, observe that the queried nodes induce a subtree of the tree and that the two chosen roots induce a path. The answer to the query is just the number of edges in the intersection of these two.

Approach 1:

We root the tree at its centroid. We consider the subtrees of the children of the centroid. The path between the two roots lies completely within one of these subtrees or lies in two of them. In the latter case, we can perform a binary search on the DFS order of these two subtrees to find the endpoints and we are done. In the first case, we simply remove the parts of the tree that don't lie within that subtree and continue to recurse until we find the answer.

If we analyze the query complexity, it turns out to be around an amortized ~4\log(N)~ queries.

Query complexity: ~4\log(N)~

Approach 2:

We employ an approach similar to the second subtask. Suppose the query on the entire tree returns a value of ~d~. We can then root the tree arbitrarily and then perform a binary search on the DFS order. This identifies one endpoint of the path. Then, we root the tree at the endpoint we found and perform another DFS order binary search to find the first endpoint.

Query complexity: ~2\log(N)+1~