Editorial for DMOPC '20 Contest 1 P5 - Victor Takes Over Canada


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: Kirito

Subtask 1

Running a brute force DFS for each query suffices.

Time Complexity: \mathcal O(NM)

Subtask 2

This is the classical problem of counting the number of distinct colours (we will be referring to guards as colours from here on) in every subtree of a rooted, coloured tree. There are several solutions to this, including:

  1. Flattening the tree into an array by using the Euler tour, and then solving the problem over an array using offline queries or persistent data structures.
  2. Small-to-large heuristic merge: Codeforces link.

These methods are not easy to extend to updates, so we will instead focus on a 3rd solution.

For every colour, sort the nodes by their position in the Euler tour. Let these nodes be a_1, a_2, \ldots, a_k.

Add 1 to each of these nodes, and for i = 1, 2, \ldots, k-1, subtract 1 from \operatorname{lca}(a_i, a_{i+1}).

Once you have finished this process for every colour, every query is just the sum of the subtree rooted at u.

The proof is left as an exercise to the reader, as it is a straightforward induction using the fact that \operatorname{lca}(a_{i-1}, a_{i+1}) is either \operatorname{lca}(a_{i-1}, a_i) or \operatorname{lca}(a_i, a_{i+1}).

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

Subtask 3

This subtask was designed to reward solutions with a suboptimal constant and those with an extra log factor.

Subtask 4

Apply the process outlined in subtask 2, maintaining the Euler tour order with an ordered set (i.e. a balanced binary search tree), and subtree sums using a range tree (e.g. a segment tree).

Time Complexity: \mathcal O((N + M)\log N)


Comments

There are no comments at the moment.