This is a problem that can be solved with an algorithm known as Mo’s algorithm on tree.

Mo’s algorithm on tree, and how to process path queries

This editorial requires the knowledge of Mo’s algorithm. For Mo’s algorithm, refer to ABC293-G editorial, for example.

Consider a length-\(2N\) sequence \(E\) obtained by traversing an Euler tour and recording the vertices when entering and exiting a vertex once each. Also construct arrays \(t_{in}\) and \(t_{out}\) representing the positions of each vertex in the sequence \(E\), for entering and exiting, respectively. Ignoring the difference of 0-based/1-based indexing, these arrays are obtained by the following Python-like pseudocode:

# g : the adjacency-list representation of the tree
E = []
tin, tout = [-1] * N, [-1] * N

def dfs(c, p): 
  tin[c] = len(E)
  E.append(c)
  for d in g[c]:
    if d == p: continue
    dfs(d, c)
  tout[c] = len(E)
  E.append(c)

We further introduce several notations for explanation.

• For a sequence \(A\), let \(A[L, R]\) be the sequence formed by the \(L\)-th through \(R\)-th elements of \(A\). If \(L \gt R\), \(A[L,R]\) is an empty sequence.
• For a sequence \(A\), let \(\mathrm{Odd}(A)\) be the set of integers occurring odd numbers of times in \(A\).
• For sets \(S\) and \(T\), let \(S \triangle T\) denote their symmetric difference, i.e. the set of elements occurring exactly one of \(S\) and \(T\).

Then the following fact holds:

Let \((S, T)\) be a pair of vertices such that \(t_{in}[S] \leq t_{in}[T]\). Then the vertex set formed by the \(S-T\) path can be represented as:

\[\mathrm{Odd}(E[t_{in}[S] + 1, t_{in}[T]])\]

with \(\mathrm{LCA}(S,T)\) inserted. (Here, one can show that the set before the insertion does not contain \(\mathrm{LCA}(S,T)\).)

(Proof)

Let \(P\) be the vertex set formed by the \(S-T\) path.
First, for any vertices \(S\) and \(T\), let

• \(A\) be the set of vertex from the root to vertex \(S\).
• \(B\) be the set of vertex from the root to vertex \(T\).

Then one can prove that their symmetric difference \(A \triangle B\) satisfies:

\[A \triangle B = P \setminus \lbrace \mathrm{LCA}(S,T) \rbrace.\]

(Proof omitted. This is true because each vertex except for the root has the corresponding edge whose “child” is that vertex.)

Also, by the property of Euler tour, \(A\) and \(B\) can be represented using \(E\) as:

\[A = \mathrm{Odd}(E[1, t_{in}[S]]), B = \mathrm{Odd}(E[1, t_{in}[T]]).\]

Hence, under \(t_{in}[S] \leq t_{in}[T]\), it follows that

\[A \triangle B = \mathrm{Odd}(E[t_{in}[S] + 1, t_{in}[T]]).\]

(End of proof)

This fact allows us to turn each query’s \(S\) and \(T\) into a segment \([t_{in}[S] + 1, t_{in}[T]]\), making Mo’s algorithm applicable. Specifically, we execute the following steps:

• Manage the parity of times each vertex \(v\) occurs within the current window, in a variable parity[v].
• Every time a segment is extended or shrunk, update parity[v], and add or remove the information regarding vertex \(x\).
• When processing a query, add the information regarding vertex \(\mathrm{LCA}(S,T)\); remove it after processing. Use an appropriate data structure to obtain \(\mathrm{LCA}\) fast.

Solution to this problem

We will explain the solution to this algorithm based on this idea.

First, we apply Mo’s algorithm on tree to transform the problem into the following:

There is a frequency array \(f_1, f_2, \dots, f_N\) for each color. Initially, all elements are \(0\). Process the following kinds of queries fast:

• Increment or decrement \(f_i\) by \(1\). It is guaranteed that \(f_i\) still satisfies \(0 \leq f_i \leq N\) by this update.
• Given \(a\) and \(b\), find the number of \(f_i\) with \(a \leq f_i \leq b\).

By simultaneously managing \(g_0, g_1, \dots, g_{N+1}\) defined by \(g_i = (\text{The number of }f_j\text{ greater than or equal to }i)\), each query can be processed in \(\mathrm{O}(1)\) time. More specifically:

• The former kind of query can be handled by updating only one value of \(g_i\).
• The latter kind of query can be obtained as \(g_a - g_{b+1}\).

By implementing this algorithm, the original problem can be solved in a total of about \(\mathrm{O}(N \sqrt{Q} + Q \log N)\) time, which is fast enough.