黒く塗られている頂点どうしの距離の最大値が考察対象となっている問題です。これは、木の直径と似た性質を持つことを以下で確認します（実際、白く塗られた葉を取り除くことを繰り返して得られる木の直径と一致しています）。

以下、空でない頂点集合 \(S\) に対し、\(S\) の直径を \(S\) に属する頂点を端点とする最長の単純パス（のひとつ）とします（特に、\(|S| = 1\) のときは長さ \(0\) のパスとなります）。本問題の各クエリで求めるものは、黒く塗られた頂点の集合の直径の長さです。

\(S, T\) を空でない集合として、\(S\) の直径の両端を \(a, b\) とし、\(T\) の直径の両端を \(c,d\) とします。\(\lbrace a, b, c, d \rbrace\) の直径が \(S \cup T\) の直径に一致することを示します。\(S, T\) の直径の選び方は複数あるかもしれませんが、どのような選び方でも構いません。以下、頂点 \(u\) と頂点 \(v\) の距離を \(d(u, v)\) と表記します。

まず、以下の補題を確認します。

補題. \(U\) を空でない集合、\(u, v\) を \(U\) の直径の端点とするとき、任意の \(w \in U\) および（\(U\) に属するとは限らない）任意の頂点 \(x\) に対して \(d(x, w) \leq \max(d(x, u), d(x, v))\)

これは、「ある頂点からの最遠点は直径の端点である」という通常の木の直径についての有名な性質と同様に示されます。

元の示すべきことに戻ると、\(S\) に属する頂点どうしの距離は \(d(a, b)\) 以下、\(T\) に属する頂点どうしの距離は \(d(c, d)\) 以下なので、\(s \in S, t \in T\) として、\(d(s, t)\) が \(\lbrace a, b, c, d \rbrace\) の直径の長さ以下であることを示せばよいです。これについては、\(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))\) であることが補題を適用することでわかります。

したがって、空でない頂点集合 \(S, T\) に対し、\(S \cup T\) の直径は \(S, T\) の直径から定数個の木上の頂点間の距離の比較により計算することができます。\(S, T\) の一方が空である場合も \(S \cup T\) の直径は \(S, T\) のうち空でないものの直径であり簡単に計算できるので、segtree に載せて計算することができます。

具体的には、segtree の区間 \([l, r)\) に対応するノードには頂点 \(l, l + 1, \ldots, r - 1\) のうち黒く塗られたものを頂点集合としたときの直径の端点（空であるときは空であることを表すデータ）を保持しておけば、クエリにおける色の変更は \(1\) 点更新、答えの取得は全体の総積という形で得ることができます。

木の \(2\) 頂点間の距離の計算は有名問題であり、\(O(N \log N)\) 時間の前計算のもと \(O(1)\) 時間で行えます。適当に根を固定して木を根付き木とし、各頂点の深さを計算しておくと LCA が計算できればよいことになりますが、これはオイラーツアーを sparse table に載せれば求めることができます。sparse table ではなく segtree に載せる方法やダブリングを用いた LCA の計算を利用した場合、LCA の計算は \(O(1)\) 時間ではなく \(O(\log N)\) 時間という評価になりますが、高速な言語・実装であれば十分 AC 可能です。

前計算に \(O(N \log N)\) 時間、各クエリに \(O(\log N)\) 時間の時間計算量であり、全体として時間計算量は \(O((N + Q) \log N)\) です。