\(N\) 頂点の木 \(T\) があり、各頂点が active / active でない の状態を持つものとします。active な頂点の集合を \(S\) で表します。
以下を処理できるセグメント木のようなデータ構造があれば、この問題を \(O((N + Q) \log (N + Q))\) 時間で解くことができます。

• \(\text{init}(T)\) : データ構造の初期化
  • \(S \gets \emptyset\) とする
  • \(T\) が \(N\) 頂点の木であるとき、\(O(N)\) 時間
• \(\text{activate}(i)\) : 頂点 \(i\) を active にする
  • \(S \gets S \cup \{i\}\) とする
  • \(O(\log N)\) 時間
• \(\text{deactivate}(i)\) : 頂点 \(i\) を active でない状態にする
  • \(S \gets S \setminus \{i\}\) とする
  • \(O(\log N)\) 時間
• \(\text{diameter}()\) : 直径を求める
  • \(\max_{x,y \in S} \text{dist}(x, y)\) が返る
  • \(O(1)\) 時間

これは、Static Top Tree を構築することで実現できます。Static Top Tree については以下の文献を読んでください。

• ABC351 G - Hash on Tree 公式解説 (by Nyaan)
• [Library Checker] Point Set Tree Path Composite Sum – maspyのHP

maspy 解説 に書かれているように、頂点 \(1\) を根とし、根の上に辺を追加して、根が virtual であるような半開パスを cluster とします。

cluster において半開区間 \([d, u)\) が expose されているとき、cluster が持つべき情報は

• 頂点 \(u\) から頂点 \(d\) までの距離
• 頂点 \(u\) から最も遠い active な頂点までの距離
• 頂点 \(d\) から最も遠い active な頂点までの距離
• cluster 内の active な \(2\) 頂点間の距離の最大値

の \(4\) 個です。cluster のマージ (rake および compress) は以下の実装例のように行うことができます。

実装例 (C++)