Editorial for Another Contest 2 Problem 3 - Poutine - Olympiads Online Judge

Editorial for Another Contest 2 Problem 3 - Poutine

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.

This problem is very similar to the classic problem of, given a weighted tree, compute the distance between pairs of vertices efficiently. The solution to that problem is to root the tree and then construct a sparse table where, for each vertex $v$ $v$ , we know the vertex that is $2^k$ $2^{k}$ vertices above it as well as the distance to that vertex. We can compute the LCA in logarithmic time and also sum the lengths in the process of computing the LCA.

For this problem, we do the same thing, except we maintain the largest and second-largest edge weights along with the ancestor information.

Comments

4

Swarley commented on Oct. 27, 2019, 10:21 p.m. ← edited →

Centroid Decomposition is also a valid solution. $\mathcal{O}(N \log N + Q \log N)$ $O (N \log N + Q \log N)$ .