Editorial for DMOPC '15 Contest 5 P5 - World Line Convergence

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 problem asks for the Divergence Factor of a POC at the moment that Okabe visits it, and the Divergence Factor of a POC is passed onto all its ancestor POCs after Okabe's visit. Knowing these, we can reword the problem as follows: for each vertex, find the sum of the Divergence Factors of all the POCs that are located in its subtree and were visited prior to it, then add 1.

At this point, the problem should feel very similar to the classical inversions counting problem. And it can be solved in the same way - using a binary indexed tree. The only difference is that instead of updating all the previous elements in an array prior to querying a particular index, we need to update the vertices in the current vertex's subtree. This can be done recursively using DFS. To avoid summing Divergence Values of vertices that are not part of the current vertex's subtree, we need to make an extra query before updating a vertex's children, then subtract this value at the end.

Time Complexity: \mathcal{O}(N \log N)


There are no comments at the moment.