この問題が青色相当の AC 人数となったことは日本競技プログラミング界隈（の一部）に衝撃を与えたことを、将来この問題に出会った方のために記しておきます。

G 問題の解説でも触れられていますが Static Top Tree を利用するのが素直な解法と言えて、コンテスト中の日本人の提出ではそれが多数です。また問題設定のシンプルさ故に類題が複数存在することもこの問題の Difficulty を下げた主要因でしょう。（例）

ここでは更なる別解、「追加クエリが容易なことに着目する」ことによる二通りの解法を紹介させていただきます。

観察

頂点の色が flip されたら具体的にどう答えが更新されるかをイメージしてみると、「黒→白」は難しいですが、「白→黒」はそこまで難しくありません。操作前の直径の端点を \((𝑢,𝑣)\) 、追加される頂点を \(𝑤\) をしたとき、操作後の直径は \((𝑢,𝑣),(𝑣,𝑤),(𝑤,𝑢)\) のいずれかとなるという話があります。これは公式解説で証明されているマージの下位互換です。

以下では「現在の直径」「現在の直径の端点ふたつ」を持たせた長さ \(3\) の整数型配列をInfoと呼びます。

上述の事実を利用すれば定数回の距離比較で Info の黒頂点追加クエリに対応できることが分かるので、木上の距離取得を \(O(1)\) でやれば \(O(1)\) で更新できます。

よって「追加クエリ」が簡単で「削除クエリ」が難しいオフラインクエリと捉えることができます。その場合以下の二つの解法が有り得ます。（以下では追加クエリを定数時間でやることを前提とします）

別解1. Segment Tree 分割統治

いわゆる「Offline Dynamic Connectivity」（ダイコネ）を一般化したテクニックです。（Segment Tree 分割統治 の詳細はABC363Gの解説で説明されています）

ダイコネでは Union Find の辺削除クエリを達成していますが、今回はその Union Find を Info にそのまま置き換え、黒頂点削除クエリを達成させます。ダイコネでは Union Find を Rollback 可能にする必要があるのと同様、Info を Rollback 可能にする必要があります。

木上の距離取得に Sparse Table を用いることにすると \(O(N\log N+Q\log Q)\) 程度です。ただし空間計算量にも（Sparse Table 部分／分割統治部分 ともに） \(\log\) が付きます。

実装例 (C++ 145ms) 139行目まではライブラリ部分です。

segtree 分割統治が思い浮かぶ方なら Static Top Tree が先に浮かぶためか、この解法による提出は見当たりません。

別解2. クエリ平方分割

コンテスト中の提出では、公式解説のやり方、Static Top Tree 、そしてこの平方分割が主な人気解法となっています。

好きな正整数 \(B\) を選んでクエリを \(B\) 個ごとのブロックに分けます。各ブロック \(O(N+Q)\) かけて各クエリ \(O(B)\) かけると、計算量は \(O(\frac{(N+Q)Q}{B}+QB)\) です。\(B=\sqrt{Q}\) とすると \(O((N+Q)\sqrt{Q})\) となり高速です。

この計算量を達成する方法を述べます。各ブロックにおける最初の処理として以下のデータを \(O(N+Q)\) 以内で前計算します。

1. 『そのブロック内でずっと黒である頂点集合』のみが黒である場合の Info

2. そのブロック内で色が変わる頂点集合

「2.」のサイズは高々 \(B\) です。よって各クエリで「1.」の Info から、「2.」内の頂点を黒ならば追加することで、各クエリ \(O(B)\) で所望の Info が得られます。

実装例 (C++ 1243ms) 79行目まではライブラリ部分です。

Segment Tree 分割統治解がクエリを二分木上に分割しているのに対し、クエリ平方分割解は \(\sqrt{Q}\) 分木上で同じことをしていると捉えることもできます。