Editorial for Another Contest 8 Problem 4 - Up and Down

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.

The intended solution is $\mathcal{O}(N^2 + Q)$ $O (N^{2} + Q)$ with a very good constant factor - this can be done with a single DFS where you track all the pairwise distances as well as the depths of all nodes in the subtree from your DFS, in which case updating the distances can be done in $\mathcal{O}(\text{depth}^2)$ $O ({depth}^{2})$ .

Comments

There are no comments at the moment.