ここで「距離」と言うときは与えられた木における距離を指します。また、色 \(c\) で塗られている２頂点の距離の最大値を「色 \(c\) の直径」と呼びます。

まず、EulerTourなどを用いた前計算をすることで２頂点間の距離を \(O(1)\) 時間で求められるようにします。

そして、与えられた木 \(T\) に対して重心分解を行ったものを \(T^\prime\) とします。

次に、各色 \(c\) について、 色 \(c\) になりうる頂点の集合を \(S_c\) とします。 \(S_c\) は元々の色が \(c\) (つまり \(A_i = c\) の頂点) と、クエリ1によって色 \(c\) で塗られる頂点の集合です。

この集合 \(S_c\) を含むLCAをベースとした Auxiliary Tree を\(T^\prime\) 上で構築します。Auxiliary Tree の頂点は、全ての色を合計して \(O((N+Q)\log{(N+Q)})\)個です。

Auxiliary Tree 上の各頂点 \(v\) に以下の情報を持たせます。

• 現在 \(v\) が色 \(c\) で塗られているかどうか
• \(v\) の子孫で現在色 \(c\) である頂点とその \(v\) との距離
• \(v\) の各子の部分木について、部分木の色 \(c\) の直径

• \(v\) の子孫で現在色 \(c\) である頂点とその \(v\) との距離

これについてはその頂点が \(v\) の \(T^\prime\) 上のどの子の部分木に含まれるかで分けて管理します

色 \(c\) の直径は、\(S_c\) を含む Auxiliary Tree の根の頂点の情報から求めることができます。

ある頂点の色を更新したとき、情報を更新する必要があるのは、重心分解した木上の祖先のみであり、その数は \(O(\log{(N+Q)})\) 個です。これらの頂点をセグメント木のようにボトムアップに更新することで各頂点の情報は \(O(\log{(N+Q)})\) 時間で更新することができます。

クレジット

原案： null0124

解法： nu50218

問題準備・解説： mono_1729

レビュー： Jinapetto

テスター： tatyam

校正： nu50218