This problem asks to handle the maximum distance between black vertices. We will first see that this is analogous to a diameter of a tree. (Indeed, it is equivalent to a diameter of the tree obtained by repeatedly removing white leaves.)

First, for a nonempty vertex set \(S\), define a diameter of \(S\) as a (any one) longest simple path whose endpoints are contained in \(S\). (In particular, if \(|S|=1\), it is a length-\(0\) path.) What is asked by a query is the length of a diameter of the vertices painted black.

For nonempty sets \(S\) and \(T\), let \(a\) and \(b\) be its both ends of a diameter of \(S\), and \(c\) and \(d\) be of \(T\). We will show that a diameter of \(\lbrace a, b, c, d \rbrace\) is equals a diameter of \(S \cup T\). There may be multiple diameters of \(S\) and \(T\), but any choice is fine. Let \(d(u, v)\) denote the distance between vertices \(u\) and \(v\).

First, we verify the following lemma:

Lemma. Let \(U\) be a nonempty set, and \(u\) and \(v\) be the endpoints of a diameter of \(U\). Then for all \(w \in U\) and all vertices \(x\) (not necessarily in \(U\)), \(d(x, w) \leq \max(d(x, u), d(x, v))\).

This can be proved in the same way as the famous property that “a vertex furthest from a vertex is an endpoint of a diameter.”

Let us come back to the original claim. Since any two vertices in \(S\) are distant by at most \(d(a, b)\), and any two vertices in \(T\) by at most \(d(c, d)\), it suffices to show that, for \(s \in S\) and \(t \in T\), \(d(s, t)\) is not greater than the diameter of \(\lbrace a, b, c, d \rbrace\). Indeed, applying the lemma asserts that \(d(s, t) \leq \max (d(s, c), d(s, d)) \leq \max (d(a, c), d(a, d), d(b, c), d(b, d))\).

Therefore, for any nonempty sets \(S\) and \(T\), the diameter of \(S \cup T\) can be computed based on diameter of \(S\) and \(T\) by comparing a constant number of pairs of vertices on the tree. Even if one of \(S\) and \(T\) is empty, a diameter of \(S \cup T\) is simply a diameter of \(S\) or \(T\), whichever nonempty, so it can be computed on a segment tree.

More specifically, each node \([l, r)\) of a segment tree stores a diameter of the vertex set consisting of the black vertices among vertices \(l, l + 1, \ldots, r - 1\) (or if the set is empty, a placeholder signifying that it is empty). This way, changing a color can be realized as an element-wise update, and obtaining the answer as a total-product retrieval.

Finding the distance between two vertices is a famous problem, and can be done in \(O(1)\) time after \(O(N \log N)\)-time precalculation. By fixing a root to regard it as a rerooting tree and precomputing the depth of each vertex, it suffices to compute the LCA (Lowest Common Ancestor), which can be done by storing an Euler tour on a sparse table. If we use a segment tree or binary lifting instead of a sparse table, finding the LCA costs \(O(\log N)\) time instead of \(O(1)\), but it still allows to solve the problem with fast languages.

The precalculation costs \(O(N \log N)\) time, and each cost can be processed in \(O(\log N)\) time, so the problem can be solved in a total of \(O((N + Q) \log N)\) time.