Editorial for DMOPC '15 Contest 7 P5 - Ariadne's Thread - Olympiads Online Judge

Editorial for DMOPC '15 Contest 7 P5 - Ariadne's Thread

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

If we start from the root node and follow the described method of traversal, the resulting order of visiting nodes is known as the Euler tour representation of the tree, which we can store in an array. From here we notice that no matter which nodes are our starting and ending points, we can divide the resultant path into segments that can be found within this array.

Our next observation should be that the required path will always visit the lowest common ancestor (LCA) of $u$ $u$ and $v$ $v$ before reaching $v$ $v$ . Keeping this in mind, we have two cases:

$u$ $u$ is visited before $v$ $v$ in the Euler tour.
$u$ $u$ is visited after $v$ $v$ in the Euler tour.

Let $x$ $x$ be the LCA of $u$ $u$ and $v$ $v$ . In the first case, it is easy to see that all nodes in the subtree rooted at $x$ $x$ that are before $v$ $v$ in the Euler tour will be visited regardless of $u$ $u$ 's position in the subtree. The length of the path is therefore the first visiting time of $v$ $v$ - the first visiting time of $x$ $x$ - the distance from $u$ $u$ to $x$ $x$ .

The second case is a little more tricky and is left to the reader as an exercise.

Time Complexity: $\mathcal{O}((N+Q) \log N)$ $O ((N + Q) \log N)$

Comments

There are no comments at the moment.