コーディング面接：Link-Cut Tree を用いて動的森を管理するにはどうすればよいか？

問題と適用範囲

辺の追加・削除が可能で、各頂点に整数値が保持されている動的森があります。link(u,v)、cut(u,v)、パスマキシマムクエリ、およびパス加算をサポートしてください。内部表現、access、makeroot、遅延タグ、正当性、および計算量を説明してください。

Sleator と Tarjan の動的木（dynamic-tree）構造は、ならし O(log n) の操作で 2 つの木を連結し、辺を切断します。面接で評価されるポイントは、テンプレートを単に暗記して答えるのではなく、表現対象の木のパスと、補助 splay 木に格納される優先パス（preferred path）を明確に区別して扱えているかです。

面接官が確認しているポイント

Link-Cut Tree が表現対象の森と、優先パスのための補助 splay 木を管理していることを理解しているか。
isRoot、push、pull、回転、および splay を正しく実装できるか。
access が表現対象の根へのパスをどのように優先パスに変換するかを説明できるか。
伝搬順序を崩すことなく、根指定のないパスに対して遅延反転タグを使用できるか。
link の前に連結性を、cut の前に対象の辺そのものを検証しているか。
ならし O(log n) を提示し、配列、再帰の深さ、ランダムテストについて議論できるか。

最初に明確にすべき質問

構造は常に森であることが保証されていますか、それとも操作によって閉路が作成される可能性がありますか？ Link-Cut Tree は一般的な動的グラフの連結性問題全般を解決するものではありません。
パス更新は加算ですか、代入ですか、あるいは最大値と最小値の両方ですか？それぞれ異なる集約および遅延タグの代数構造が必要です。
値は頂点上にありますか、それとも辺上にありますか？辺の値が必要な場合は、辺を仮想頂点として表現します。
永続性や並行性は必要ですか、それともシングルスレッドのオンライン構造ですか？
入力に重複した link、存在しない cut、または自己ループが含まれる可能性はありますか？

30秒での簡潔な回答

表現対象の頂点ごとに 1 つの補助 splay を使用します。ch は splay の子を保持し、fa は補助木の親または表現対象パスの親のいずれかになります。access は上方向に走査し、各右の子を処理済みパスで置き換えます。makeroot は補助木にアクセスして遅延反転を行います。link は連結性を確認し、一方の端点を makeroot して接続します。cut は一方の端点を makeroot し、もう一方に access して、左部分木が正確にその辺の端点であることを確認した上で切断します。回転の前に push し、更新の後に pull します。各操作はならし O(log n) です。

ステップごとの詳細解説

1. 2 つの木の関係性を表現する

補助 splay の子は優先パス上の順序を表します。ノードが補助木の根である場合、fa は splay の親ではなく、表現対象の木におけるパスの親（path parent）となります。したがって、isRoot(x) は fa[x] が単に 0 であるかどうかだけでなく、x が fa[x] のいずれの子でもないことを判定しなければなりません。

2. 集約と遅延タグの維持

パスの最大値について、pull(x) は x における値と両方の補助部分木を組み合わせます。パス加算には add タグを使用し、パス反転は rev タグの下で子ノードをスワップします。push は加算の前に反転を伝搬するか、または合成順序が正しく定義されている必要があります。

text

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. access の実装

last = 0 を設定し、x から fa を通って上方向に走査します。y を splay し、y の右の子を last に設定し、y を pull してから、last を y に更新して処理を続けます。最後に元の x を splay します。これで x から表現対象の根へのパスが 1 つの優先パスとなり、その splay の順序によってパス集約に答えることができます。

4. makeroot の実装

makeroot(x) は access(x) を呼び出し、x に rev を適用します。x が表現対象の木の根になるため、link(x,y) で 2 つの木を意図した方向に結合できるようになります。表現対象の木を再帰的に反転させる必要はありません。補助 splay が遅延反転を保持できます。

5. link と cut の実装

link(x,y) は makeroot(x) を呼び出し、findroot(y) == x を拒絶した上で、fa[x] = y を設定します。cut(x,y) の場合は、makeroot(x) と access(y) を呼び出します。辺が存在する場合、y の左の子は x であり、x には右の子がありません。その子を切り離し、その親ポインタをクリアします。この構造チェックにより、パス上の異なる辺を誤って切断するのを防ぎます。

6. パスのクエリと更新

split(x,y) は makeroot(x); access(y) であり、y の補助 splay が x から y へのパスを表す状態になります。最大値を得るには mx[y] を読み取り、パス更新を行うには y に applyAdd を適用します。優先パスを元に戻す必要はありません。次回の access が適切に再編成します。

7. 計算量とテスト

Sleator–Tarjan の解析により、link、cut、root、evert の各操作はならし O(log n)、空間計算量は O(n) となります。小規模な実装を作成し、単純な隣接リストによる森の実装とクロスチェックを行います。有効な link と cut を生成し、パス最大値と加算を比較します。単一頂点の木、繰り返しの makeroot、連続した access、無効な cut、重複する値、負の値などもテストケースに含めます。

質の高い模範解答

表現対象の木を通常の二分木として扱うのではなく、fa が補助木の親または表現対象パスの親のいずれかを意味するようにし、両者を isRoot で区別します。各 splay ノードはその値、部分木の最大値、反転タグ、加算タグを保持します。access は優先パスを露出し、makeroot はそれを遅延反転し、split(x,y) は y の splay に x から y へのパスを表現させます。

link は makeroot を実行し、すでに連結されている端点は拒絶します。cut は makeroot と access を実行した後、y の左部分木が正確に x であることを確認してから切断します。回転の前に祖先ノードを push し、変更後に pull します。この構造はならし時間 O(log n) と空間 O(n) を使用します。ナイーブな森の実装に対するランダムなクロスチェックにより、集約、無効な操作、遅延タグの組み合わせを網羅的に検証します。

よくある落とし穴

補助木の根の判定に fa[x] == 0 を用いる → パスの親が 0 以外になることがあるため、子ノードに基づく isRoot の判定を用いる必要があります。
回転前の祖先への push を省略する → 反転や加算が未反映のまま残るため、祖先を収集して逆順に push します。
辺の確認をせずに cut を実行する → パス上の誤った辺が削除されるため、makeroot/access の後に左部分木の形状を検証します。
連結性チェックを行わずに link を実行する → 閉路が発生して森の不変条件が壊れるため、事前に根を比較します。
access 後の splay を表現対象の木全体として扱ってしまう → 露出されるのは 1 つの優先パスのみであるため、以降の access 操作に任せる必要があります。
クエリのみをテストして更新をテストしない → 遅延タグのバグが見逃されるため、ランダムなパス加算をナイーブな森と比較します。

フォローアップの質問と回答

パスの最小値や XOR を管理するにはどうすればよいですか？

pull を必要なモノイド集約に置き換えます。XOR は反転操作において順序に依存しませんが、非可換な集約の場合はパスの方向と反転順序を明示的に定義する必要があります。

辺の重みを扱うにはどうすればよいですか？

各辺を、値がその辺の重みである仮想頂点に分割し、通常の頂点集約を使用します。link および cut の際にその仮想頂点を管理します。

なぜ access は古い右部分木を置き換えることができるのですか？

古い部分木は、表現対象パスの親として fa を通じて接続されたまま残ります。単に優先パスではなくなっただけです。補助木の子関係とパスの親関係は分離されています。

パス代入をサポートできますか？

過去の加算を上書きし、値と最大値を更新し、定義された順序で反転と合成される代入タグを追加します。タグの代数構造は明示的でテスト可能でなければなりません。

なぜ findroot は正しく動作するのですか？

access(x) の後、タグを push しながら最も左の子をたどって最左の補助ノードに到達します。そのノードが表現対象の根となります。その後の操作を安定させるために、そのノードを splay します。

Link-Cut Tree を避けるべきなのはどのような場合ですか？

静的な森であれば、DFS/オイラーツアーや Heavy-Light Decomposition（HLD）の方が単純です。一般的な動的グラフの連結性、並行性、または永続性が必要な場合、保守の複雑さや実装リスクがメリットを上回る可能性があります。