Editorial for Cheerio Contest 3 P5 - Train Network
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
This subtask was meant to reward simple brute force solutions.
Time Complexity:Subtask 2
Once again, a brute force solution should suffice. For each query, we can run bfs on the resultant graph (initial tree plus the line) to find the shortest distance.
Time Complexity:Subtask 3
Let . In the initial tree, the shortest path from
to
is
. Notice that after adding the line, it is still the shortest path that passes through
. Thus, in order to travel from
to
in a potentially shorter distance, we cannot travel through
. Since removing
would disconnect the subtrees rooted at the children of
, we would need to use the line to travel between them. In particular, the track(s) we must use are the ones on the line that connect adjacent subtrees because they are bridges. This observation is crucial because we only need to perform
bfs traversals instead of
. For each node
, we run bfs on the graph (initial tree plus the line at
's depth), storing the distance to each node
in
. Now, for some node
(
is the endpoint of a bridge), we can calculate the distance as
. One possible value of
that yields the shortest distance is the left/rightmost node at depth
in
(
is the subtree rooted at the child of
that contains
).
Comments