beet's soil

競プロのことなど

Link Cut Tree まとめ

そのうちちゃんと書きます（うしくんが）

リンク集

これ以上のことをやりたければ基本的にTopTreeを書いた方がいいと思います

お気持ち

LCT では、元の木をパスに分解して、分解したパスを 平衡二分木（Splay木）で管理します

細かいテクニック

上の記事は全部頂点属性です。辺属性にする場合は二つ選択肢があって

  1. 各辺をその下側の頂点に対応させる（根変更不可、定数倍が軽い）
  2. 頂点倍加をして辺に対応する頂点を作り、元々の頂点には単位元を載せる（根変更可、定数倍が重い）

辺を切る場合は cut でいいんですが、頂点を消したり戻したりする操作もシミュレートできる場合があって（愚直にやるとウニの真ん中を消したり戻したりしようとした時に大変なことになる）

  1. 頂点を消す場合はその頂点と親との間の辺を切る
  2. vを含む連結成分についてのクエリは expose(v) して splay 木をDFS して根の直下の頂点を持ってきて、そこと根の間の辺を cut する、クエリに答え終わったら link して戻す

↑上で元々の木の根に対して 1. をしようとすると困るので、頂点を一つ足してそいつを新しい根にして元の根と繋ぐといいです

あとなんか思い出したら書きます