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, \dots, a_k~.

Add 1 to each of these nodes, and for ~i = 1, 2, \dots, 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)~