Subtask 1

We can model the prison as a graph where the vertices are the rooms and the edges are the passageways. For each query, we can perform a depth first search to get all vertices on the path from ~a_i~ to ~b_i~ (ignoring ~b_i~) and all vertices on the path from ~c_i~ to ~d_i~. We can then find the first index in the two paths where the vertices are the same.

Time Complexity: ~\mathcal{O}(N \cdot Q)~

Subtask 2

In this subtask, the graph is a line. We can deal with the queries by checking the midpoint of ~a_i~ and ~c_i~ (if it exists) and seeing if it will be reached before Besley reaches ~b_i~ and the guard reaches ~d_i~ and if they will meet that midpoint at the same time. It can be seen that there is no other point where they can meet.

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

Subtask 3

For each vertex, we can store the minimum distance to any vertex on the path from ~1~ to ~N~, as well as the distance to vertex ~N~. We can see that the answer only exists if the distance of vertex ~c_i~ from vertex ~N~ is equal to the distance of vertex ~1~ from vertex ~N~, and the distance from vertex ~c_i~ to the path is not equal to the distance from vertex ~c_i~ to vertex ~N~. If these conditions are satisfied, then the answer is equal to the distance from vertex ~c_i~ to the path.

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

Subtask 4

In this subtask, Besley and the guard will meet only if the path from ~c_i~ to ~d_i~ intersects the path from ~1~ to ~N~. If the tree is rooted at vertex ~N~, then they only intersect if the lowest common ancestor of ~c_i~ and ~d_i~ is on the path from ~1~ to ~N~ (it is possible to do this without traditional lowest common ancestor algorithms). It can be seen that when this happens, the path from ~c_i~ to ~d_i~ will intersect with the path from ~1~ to ~N~ over some path of vertices. We can then use a method similar to subtask 2 to determine if they will meet on this path, adjusting for the time the guard first reaches the path from ~1~ to ~N~.

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

Subtask 5

In this subtask, we can root the tree at vertex ~N~. Besley and the guard will only meet if the depth of ~a_i~ and ~c_i~ are the same. They will first meet at their lowest common ancestor as long as it is not vertex ~N~. The answer is the difference between the depth of ~a_i~ and the lowest common ancestor of ~a_i~ and ~c_i~.

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

Subtask 6

Special thanks to 300iq for providing the idea behind this solution.

It can be proven that if a solution exists, it will always be the middle vertex ~x~ on the path from ~a_i~ to ~c_i~. ~x~ can be found by first finding the distance between the two vertices using the lowest common ancestor (~\text{lca}~), and then selecting the middle vertex in ~\mathcal{O}(\log N)~ using any standard method (binary lifting, heavy light decomposition, etc…). The distance between two vertices ~u~ and ~v~ in a tree is ~\text{depth}(u) + \text{depth}(v) - 2 \cdot \text{depth}(\text{lca}(u, v))~. Here, a solution exists if and only if ~x~ is on both the path from ~a_i~ to ~b_i~ and on the path from ~c_i~ to ~d_i~ and is not ~b_i~ or ~d_i~. We can check if vertex ~x~ is on a path from vertices ~u~ to ~v~ by checking if the set ~\{\text{lca}(x, u), \text{lca}(x, v)\}~ is the same as the set ~\{\text{lca}(u, v), x\}~. We can query for the lowest common ancestor (~\text{lca}~) in ~\mathcal{O}(1)~ time with ~\mathcal{O}(N)~ or ~\mathcal{O}(N \cdot \log N)~ precomputation using any data structure that supports range minimum queries over Euler tour indices.

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