Subtask 1

For each query, we can root the tree and count the number of distinct elements in each subtree.

To do so quickly, we can initially store every element in a set data structure, and do a DFS, merging the sets of all elements in the subtree. This takes ~\mathcal O(QN^2)~ time, however, we can optimize this by merging the smaller set into the larger set.

To prove this works, note that every time an element is inserted into a new set, the new set must have at least double the size of the old set. We start with sets of size 1, so we can double this at most ~\mathcal O(\log N)~ times. Thus the time complexity for each query takes ~\mathcal O(N \log N)~ time.

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

Subtask 2

There are multiple approaches to this subtask, but we will be covering the one that extends most naturally to the final subtask.

Note that as ~K~ is fixed, there are at most ~N~ distinct queries, so we can compute all ~N~ possible answers and answer the queries using a lookup table.

The key observation is that, when the tree is rooted at ~r~, and you want to reroot to a direct descendant ~d~, only two subgraphs are affected: the subtree rooted at ~d~ before rerooting, and the subtree rooted at ~r~ after rerooting. Note that these are in fact complements of each other, so for every subtree (when we are rooted at ~1~), if we can count the number of distinct elements in its subtree and the complement of its subtree, we can compute all queries with a simple DFS.

Root the tree arbitrarily, and using the small-to-large merging trick from the first subtask, we can count the number of distinct elements in each subtree. To count the number of distinct elements in the complement, we can employ complementary counting: that is, we can find the number of elements that occur only in the subtree.

This can also be done in ~\mathcal O(N \log N)~, by using a frequency counter and employing the small-to-large merging technique outlined in subtask 1.

Time Complexity: ~\mathcal O(N \log N + Q)~

Subtask 3

For subtask 3, we process the queries offline, in DFS traversal order.

Again, reroot the tree arbitrarily, and using the observation outlined in subtask 2, compute the number of distinct elements in each subtree and its complement in ~\mathcal O(N \log N)~.

This time, we can key a range tree by the number of subtrees that have exactly ~d~ distinct elements for ~d = 1, \dots, N~. Using the same observation as subtask 2, we note that we decrease the number of subtrees with ~s_v~ elements by 1, and increase the number of subtrees with ~s_{v^c}~ elements by 1, where ~s_v~ is the number of distinct elements in the subtree rooted at ~v~, and ~s_{v^c}~ is the number of distinct elements in its complement.

Finally, each query can be answered in ~\mathcal O(\log N)~ time by querying how many subtrees have ~k_i, k_i + 1, \dots, N~ distinct elements.

Time Complexity: ~\mathcal O(N \log N + Q \log N)~