## Editorial for Cheerio Contest 3 P5 - Train Network

**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.**

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 ).

**Time Complexity:**

## Comments