Editorial for Cheerio Contest 3 P5 - Train Network

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.

Author: rickyqin005

Subtask 1

This subtask was meant to reward simple brute force solutions.

Time Complexity: \mathcal{O}(N^3+Q)
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: \mathcal{O}(NQ)
Subtask 3

Let C = \text{lca}(A, B). In the initial tree, the shortest path from A to B is A \longrightarrow C \longrightarrow B. Notice that after adding the line, it is still the shortest path that passes through C. Thus, in order to travel from A to B in a potentially shorter distance, we cannot travel through C. Since removing C would disconnect the subtrees rooted at the children of C, 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 N bfs traversals instead of Q. For each node i, we run bfs on the graph (initial tree plus the line at i's depth), storing the distance to each node j in \text{dis2}[i][j]. Now, for some node G (G is the endpoint of a bridge), we can calculate the distance as \text{dis2}[G][A]+\text{dis2}[G][B]. One possible value of G that yields the shortest distance is the left/rightmost node at depth D in S (S is the subtree rooted at the child of C that contains A).

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


There are no comments at the moment.