LCTまとめ

参照
\(LCT\)
\(LCT\)は\(Splay\)によってメンテナンスされていますが、その使い方は非常に柔軟ですので、\(LCT\)を上手に使うには、\(Splay\)の構造を把握しておく必要があります.
テンプレート
Luogu 3690【テンプレート】Link Cut Tree(ダイナミックツリー)
Luogu 2147[SDOI 2008]洞窟探査
Luogu 3203[HUNOI 2010]弾き飛ぶ羊/CF 13 E Holes
ツリーチェーンの情報を維持する
主にデータ構造の操作で、より良いデータ構造の基礎が必要です.
メンテナンスのマークに注意して、\(pusshdown\)と\(udate\)を忘れないようにして、マークを押しながら更新する原則で処理します.
Luogu 1501[国家合宿隊]Tree II
Luogu 2486[SDOI 2011]カラーリング
Luogu 4332[SHOP 2014]三叉神経樹
メンテナンスサイドダブル接続量
接続操作をサポートしています.テーマが切断されている場合は、オフラインで逆処理できます.
二重連結成分が出たら、直接にチェーンを取り出して、一つの点を使って、それを使ってメンテナンスを調べます.注意してください.\(access\)時に更新します.
Luogu 2542[AHOI 2005]航路計画
ふちけんを守る
辺を一つの点として、\(a\rightarrow b\)のように、\(a\rightarrow c\rightarrow b\)を使って、\(c\)にサイド情報を記録することができます.この方法でツリーを維持することができます.
Luogu 4234最小差分値生成ツリー
サブツリーのメンテナンス情報
同時に虚、実のサブノードを維持し、新たに一つの変数で虚子ノード情報を記録し、サブノードの虚実変換の過程でこの変数を更新します.
虚子ノードの情報も一つのノードに影響を与えますので、父に情報をアップロードするように注意してください.
例:

void link(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
    fa(x)=y;
    s2(y)+=s(x);
    update(y);
}

上のコードには\(access(y)、splay(y)\が不可欠です.これを追加しないと、更新されたのはそのノードがその場所にいる\(Splay\)の情報だけです.この\の祖先の情報を更新できないので、先に\(access(y)、splay(Spy)は、(splay)のチェーンの存在を直接にしません.このようにして更新することができます.すべてのタグが必要とされるノードが利用できるようにします.
Luogu 4219[BJOI 2014]大融合