This problem can be solved by adapting Mo’s algorithm for tree path queries.

How to adapt Mo’s algorithm for tree path queries

This explanation assumes prior knowledge of Mo’s algorithm. For information on Mo’s algorithm, please refer to the editorial for ABC293-G.

We consider an array \(E\) with \(2N\) elements. Each vertex is included in \(E\) exactly twice, i.e. when its subtree is entered and exited during an Euler tour. Refer to the following Python-ish pseudocode:

# g: The tree as an adjacency list
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)

Now consider the path between vertices \(S\) and \(T\) where \(t_{in}[S] \le t_{in}[T]\). Then consider the subarray of \(E\) for indices \([t_{in}[S] + 1, t_{in}[T]]\). Each vertex on the path from \(S\) to \(T\), except for \(\mathrm{LCA}(S, T)\), will appear in this subarray exactly once. All other vertices, including \(\mathrm{LCA}(S, T)\), will appear either \(0\) or \(2\) times.

In other words, the path between \(S\) and \(T\), except for the LCA, are exactly the vertices that appear in this subarray an odd number of times.

Explanation / proof sketch: The subarray starts just after the Euler tour enters the subtree of \(S\). The tour then exits the subtrees of all nodes from \(S\) to the LCA, excluding the LCA, then enters the subtrees of all nodes from the LCA to \(T\), excluding the LCA. If other nodes are visited, their subtrees are also exited before the end of the subarray.

Thus we can convert each path query from the form \((S, T)\) to \((t_{in}[S] + 1, t_{in}[T], \mathrm{LCA}(S, T))\) and apply Mo’s algorithm to the paths in the tree, via the following steps:

• Let parity[v] represent the parity of the number of times vertex \(v\) appears in the subarray.
• When the subarray is stretched or shortened, we toggle parity[v] and add or remove information related to \(v\), depending on the parity.
• When processing a query, we add the information related to the LCA, answer the query, and then remove that information.

Solution to this problem

Based on the above, we will now consider the solution to this problem.

First, by applying Mo’s algorithm as above, we can reduce to the following problem.

There is an array \(f_1, f_2, \dots, f_N\) representing the frequency of each color. Initially, all elements are \(0\). Process queries of the following types quickly:

• Given \(i\), increase or decrease \(f_i\) by \(1\). (\(0 \le f_i \le N\) holds after each operation.)
• Given \(a, b\), output \(|\{y : a \le f_y \le b\}|\).

We could do this by maintaining a second array \(g_0, g_1, \dots, g_{N+1}\) such that \(g_i = |\{y: f_y < i\}|\).

• For the first operation, \(f_i\) increases or decreases by \(1\), thus \(g\) can be updated in \(O(1)\).
• For the second operation, the answer is \(g_{b+1} - g_a\).

The problem is thus solved in \(O(N \sqrt Q + Q \log NQ)\) time.