基本操作

LCT（リンクカットツリー）は、Splay木を使用して森を管理します。実際のエッジの追加や削除が可能です。親への参照のみを行い、子への参照はしません。

• notroot: ノードがSplay木のルートである場合は0を、それ以外は1を返します。ノードがルートであるときには特別な扱いが必要なためです。
• splay: 現在のノードを現在のSplay木のルートに回転させます。
• Access: 現在のノードから森のルートまでのパスを全て実エッジに変更します。
• make root: 現在のノードを森の新しいルートにします（反転マークを使用）。
• find root: 現在のノードが属する木のルートを探し、同時にそのノードに対してAccessを行います。
• Split: ノードxからノードyまでのパスを取り出します。xは根（最も浅い深さ）であり、yはxのSplay木内にあり、Splay木のルートです。
• Link: ノードxとyを接続します（既に接続されている場合は無視）。
• Cut: エッジ(x, y)を削除します（存在しない場合は無視）。

性質

• LCTは森を管理し、それぞれの木は実エッジも虚エッジも持ち合わせていません。
• 各木は多くの実エッジに分割され、それぞれの実エッジはSplay木によって維持されます。隣接する実エッジのSplay木の頂点は上の実エッジに虚エッジで接続されます。
• Splay木のルートだけが正しい情報を保持しており、Splay木内部の情報はほとんど間違っています！しかし、Splay木の中順走査は深さの昇順にソートされています。

例題

P3690 【テンプレート】Link Cut Tree （動的木）

P2147 [SDOI2008]洞穴勘測

この問題ではLinkとCutが常に合法であることが保証されています。書き方を学ぶことができます。

P1501 [国家集訓隊]Tree II

区間加算、乗算マーク（線形セグメントツリーに似ています）が必要です。

LinkとCutが常に合法であることが保証されています。

P3950 部落衝突

P4332 [SHOI2014]三叉神経木

LCTは葉から根までのパス情報を維持します。動的木は静的木を維持します

動的最小生成木の維持:

P4172 [WC2006]水管局長

問題文:

単純な無向グラフが与えられます。エッジの削除と、xからyまでのパス中の最大エッジコストの中で最小のものを求める操作をサポートします。

解説:

エッジの追加をサポートする場合、最小生成木森林を維持します。エッジを追加するときに、サイクルを作らない場合は追加します。サイクルを作り、サイクル内の最大エッジコストが追加しようとしているエッジよりも小さい場合は何もしないです。サイクル内の最大エッジコストが追加しようとしているエッジよりも大きい場合は、そのエッジを削除し、新しいエッジを追加します。

エッジの削除のみをサポートする場合は、逆順に処理すればよいです。

xからyまでのパス中の最大エッジコストを見つけるための良い方法は、エッジをノードに変換することです。各ノードはval、mxid（val: ノードであれば影響を与えない値、例えば0または-infを設定）（mxid:部分木中の最大ノードコスト）を維持します。また、各エッジが接続するノードを見つけるために、各エッジに対してU、Vを維持します。そしてLCTの標準的な操作を行います。

P4234 最小差値生成木

最小値を確定した後、合法なエッジの最小生成木を求めます。

エッジをコストの降順にソートし、最小生成木を動的に維持します。

P4180 [BJWC2010]厳密次小生成木

次大値を維持し、Kruskal法をシミュレートし、サイクルを見つければよいです。

辺二重連結成分の維持:

P2542 [AHOI2005]航线計画

エッジの追加のみをサポートします。

エッジをノードに変換するアイデアを使用します。

すべての辺を表すノードを初期化し、サイクルを作らない場合は追加します。サイクルを作った場合は追加せず、サイクル上のすべてのノードを「橋でない」とマークします。

2959: 長距離ランニング

問題文:

単点更新、エッジの追加、辺二重連結成分ツリーのチェーン上の重みの合計のクエリをサポートします。

解説:

サイクルを作った場合は、直接DFSで縮点します。

一部のノードのfaが空を指す可能性があるため、追加の辺二重連結成分のUnion-Findを維持します。

元グラフの部分木の維持

各ノードはすべての虚子孫の情報を付加します。エッジの実/虚の変更に関連する操作を行う際には特に注意が必要です。

LCTは部分木情報を維持できますが、部分木情報を変更することはできません。したがって、部分木に関する問題でエッジの追加/削除が関与しない場合は、木の鎖分割を使用するのが便利です。

P4219 [BJOI2014]大融合

//siz : 仮想の子孫のみの情報（サイズを例とする）
//Siz : 部分木情報（自分自身、実子孫、仮想の子孫を含む）
inline void pushup(int node) {
    Siz[node] = siz[node] + Siz[son[node][0]] + Siz[son[node][1]] + 1;
}
inline void Access(int node) {
    for (int parent = node, last = 0; parent; last = parent, parent = fa[parent])
        splay(parent), siz[parent] += Siz[son[parent][1]], son[parent][1] = last,
        siz[parent] -= Siz[son[parent][1]], pushup(parent);
}
inline void Link(int x, int y) {
    make_root(x);
    make_root(y);
    fa[x] = y, siz[y] += Siz[x];
}

応用：動的重心の維持：P4299 首都

ツリー上の同色連結成分の維持

SP16549 QTREE6 - Query on a tree VI

各色に対して1つのLCTを維持することを考えることができます。ただし、これを単にすると色を変更する1回の操作の複雑さは O(d log n) になり、菊花グラフで落ちてしまいます。

各点の色をエッジに移すことで、xの色がcである場合、c番目のLCT上でxからfath(x)にエッジを張ります。ここでfath(1) = n+1です。これにより、最上位のノード以外の連結成分内の他のノードの色もxと同じになります。そこでAccess(x)を行い、実部分木のサイズを返します。

inline void Link(int x, int y) {//yはxの親
    splay(x);
    Access(y); splay(y);
    fa[x] = y; siz[y] += Siz[x]; pushup(y);
}
inline void Cut(int x, int y) {//yはxの親
    Access(y); splay(y);
    splay(x);
    siz[y] -= Siz[x]; fa[x] = 0; pushup(y);
}