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

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

##### Subtask 1

Running a brute force DFS for each query suffices.

**Time Complexity:**

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

- 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.
- 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 .

Add 1 to each of these nodes, and for , subtract 1 from .

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

The proof is left as an exercise to the reader, as it is a straightforward induction using the fact that is either or .

**Time Complexity:**

##### 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:**

## Comments