リンク-カット木 (Link-Cut Tree) : コード付き

まえがき

この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)

リンク-カット木とは

リンクカット木は、森 (各連結成分が木のグラフ) に対して以下のクエリに答えることができるデータ構造です。

• ある木の根を始点とするパスに対するデータ取得
• ある木の部分木に対するデータ取得 (今回は扱わない)
• 辺を追加 (追加後も森である必要がある)
• 辺を削除
• ある木の根を変更する

辺を動的に追加/削除することから、このデータ構造は動的木または動的森と呼ばれるデータ構造に属します。

また、この記事を読むための前提として Splay Tree ( こちらの記事 (平衡二分木入門 : Splay Tree) ) を $30$% ぐらい理解しているといいと思います。

説明

競技プログラミングにおいて、根付き木は隣接リストや、親頂点を管理する配列で表現するのが典型的です。隣接リストによる表現が高い汎用性を持つのに対して、親頂点を管理する方法は LCA や パス取得などの処理に特化しています。このように、どのように木を管理するかは、実現したい処理によって使い分けるのが良いです。

今回、リンク-カット木 (以降は LCT とする) は パスに対するデータ取得 を行うものとして、パスに対するデータ取得に特化した LCT を説明します。

森の構築

辺が $1$ つもない状態からはじめ、辺を追加して森を構築していきます。

図 1

ここで重要なことを言います。LCT においては、森の実体を直接保管しないという特徴があります。どういうことかというと、LCT では木の辺を直接管理しないというトリッキーな方法を取ります。例えば、以下 (図 2) のように木を構築してみます。

図 2

この例では、LCT が管理するデータが、ちょうどたまたま、表現したい木と同じ形になっています。後でこの形は崩れていきます。なお、赤い辺のことを heavy-edge、緑の辺を light-edge と言います。

補足 1

本来は 遅延評価(後述) によって、LCT が持つデータに未評価部分が存在しますが、図 2 では見やすさのために全ての遅延評価を評価して解消しています。

なお、後に説明する link というメソッドを以下の順に実行することで図 2 の木を得ることができます。

link(8,9);
link(8,7);
link(7,2);
link(7,6);
link(1,6);
link(1,3);
link(3,4);
link(3,5);

heavy-edge と light-edge

LCT は heavy-edge と light-edge を駆使して木をパスに分解して管理します。この記事では赤い辺を heavy-edge に、緑の辺を light-edge に対応させて説明します。

heavy-edge は ひとまとまりのパスを管理するデータ構造 を成し、light-edge は 分解したパス同士の関係 を表します。例えば、図 2 は以下のようなパスの集まりに分解できます。長方形の枠で囲った部分がひとまとまりのパスに対応します。

図 3

パスは $1$ 直線なので、各パスを Splay Tree で表現できます。具体的には、左の頂点ほど LCT が表現する木の根に近く、右の頂点ほど LCT が表現する木の根から遠いという順序をもつ Splay Tree で表現します。heavy-edge とは、この Splay Tree の辺のことなのです。

図 4

そして、light-edge もまた Splay Tree の辺の亜種です。Splay Tree は根付き木なので、 Splay Tree の辺の $2$ つの端点のいずれかは親頂点で、他方が子頂点という関係をなします。通常の Splay Tree の辺、すなわち heavy-edge は親と子を双方向に接続する無向辺であるのに対して、light-edge は子頂点から親頂点に向けて一方的に接続する有向辺です。つまり、light-edge で繋がれた子頂点側からは親頂点にアクセスできますが、親頂点側からは子頂点にアクセスできません。

なおこの記事では、LCT が表現する木の根と、パスを管理する Splay Tree の根を区別するために、単に根と書いたときは LCT が表現する木の根を表すことにして、Splay Tree の根を指す場合は省略せずに Splay Tree の根と書きます。辺についても同様の表記としますが、単に heavy-edge や light-edge と書いた場合は暗黙的に Splay Tree の辺であることとします。

実行できるメソッドたち

まず、最も基本的なメソッドとして以下を定義します。

• $\mathrm{access}(x) := $ 木の根から頂点 $x$ までパスを繋ぐ。
  • 繋げたパスも Splay Tree で管理されるので、頂点 $x$ を splay してその Splay Tree の根にすることで、頂点 $x$ からパス全体のデータの集約を取得できるようにする。

$\mathrm{access}(x)$ では、以下の $3$ つの手続きでイテレーションを行います。ちゃんと読み込まなくても、図による $\mathrm{access}$ の様子を見ればなんとなくわかると思います。

1. 以下の方法で頂点 $x$ を splay し、その結果、頂点 $x$ から Splay Tree における親方向に辺が出てなければ、$\mathrm{access}$ の手続きを終了する。
   • light-edge は回転させない。
   • heavy-edge の回転による Splay Tree の辺の張り替えにおいて、Splay Tree で親方向に伸びる light-edge であれば通常の Splay Tree と同様に行う。(親方向以外の light-edge は回転するアクターの頂点からはアクセスできないので無視する。)
   • splay した後、頂点 $x$ から Splay Tree における右の子頂点への辺が存在すれば、それを light-edge にする。つまり、Splay Tree における右の子頂点へのアクセスを無くす。
   • 頂点 $x$ から light-edge で親頂点に接続している状態になれば、この手続きを終了する。
2. 頂点 $x$ から light-edge で接続している親頂点を頂点 $y$ として、頂点 $y$ を splay する。splay の方法は手続き $1$ と同じ。
3. 頂点 $y$ の Splay Tree における右の子を頂点 $x$ にする。
   • 頂点 $x$ から伸びていた light-edge がこのタイミングで heavy-edge になり、$2$ つの Splay Tree がマージされる。
   • Splay Tree の右の子は $1$ つ以下なので、右の子の変更は heavy-edge の張り替えを意味している。

以上の手続きが終了したとき、根から頂点 $x$ までのパスが $1$ つの Splay Tree で表現されており、頂点 $x$ はその Splay Tree の根になっています。以下に $\mathrm{access}(9)$ の様子を示します。

ステップ 1 (図 5 : 手続き 1)

はじめ、頂点 $9$ は単体の Splay Tree なので特別なこともなく splay を完了させます。

ステップ 2 (図 6 : 手続き 2)

頂点 $9$ から light-edge で頂点 $8$ につながっているので、頂点 $8$ を splay します。このとき、light-edge は回転させないことと、Splay Tree の親方向につながる light-edge は heavy-edge と同様に辺の張り替えが行われることに注意してください。この例では、元々頂点 $6$ から出ていた light-edge は頂点 $8$ に受け継がれます。

ステップ 3 (図 7 : 手続き 3)

手続き $2$ で splay した頂点 $8$ の右の子を、$\mathrm{access}$ する頂点である頂点 $9$ に変更します。これによって $2$ つのパスがマージされました。

ステップ 4 (図 8 : 手続き 1 と手続き 2)

手続き $1$ に戻り、頂点 $9$ を splay し、その後頂点 $9$ から light-edge で接続されている頂点 $1$ も同様に splay します。

ステップ 5 (図 9 : 手続き 3)

手続き $2$ で splay した頂点 $1$ の右の子を、$\mathrm{access}$ する頂点である頂点 $9$ に変更します。元々 heavy-edge があった ($1$ - $3$) から heavy-edge が張り変わっていることが確認できます。

ステップ 6 (図 10 : 手続き 1)

頂点 $9$ を splay し、その結果、Splay Tree における親方向に辺が出ていなくなったので手続きを終了します。

これによって、頂点 $1$ から頂点 $9$ までのパスを $1$ つの Splay Tree で表現することができました。現在の木のパスは以下のように分解して管理されています。

図 11

Splay Tree でパスを表現できたので、パスに関して様々な計算を行うことができます。例えば、パスの長さ (辺の個数) はそのパスを管理する $\mathrm{Splay Tree}\space のサイズ - 1$ です。

連結成分の根の特定

頂点 $x$ が属する連結成分の根が不明の場合、$\mathrm{access}(x)$ によって根 (不明) から頂点 $x$ までのパスを Splay Tree で構築し、その Splay Tree の最も左の頂点を取得することで、連結成分の根を取得できます。Splay Tree の最も左の頂点の取得は Splay Tree のメソッドで処理可能です。

$2$ つの頂点が同じ連結成分に属するかどうかも、それぞれの頂点の属する連結成分の根を見て判定することができます。

連結成分の根の変更

連結成分の根の変更メソッドとして、以下を定義します。

• $\mathrm{evert}(x) := $ 頂点 $x$ が属する連結成分の根を $x$ に変更する。

手続きはシンプルで、以下の $2$ ステップからなります。

1. $\mathrm{access}(x)$ する。結果、頂点 $x$ が Splay Tree の根になる。
2. 頂点 $x$ に 左右反転の遅延評価 をかける。

例えば頂点 $9$ を連結成分の根にする場合、まずは $\mathrm{access}(9)$ によって根からのパスを構築します。

図 11 と同じ図

その後、頂点 $9$ に左右反転の遅延評価をかけます。

図 12

パスを管理する Splay Tree を、木の根に近い頂点ほど左にあるという順序で構築していたので、パスを左右反転すると、その影響で自動的に木の根が変更されます。

図 13

補足 2

左右反転の遅延評価があることでわかりやすり図示が困難になってしまうので、以降は遅延評価を全て評価して解消した状態の図を見せます。

図 14

親頂点の特定

連結成分の根の特定と同様の手法で可能ですが、紹介するアルゴリズムのバリエーションのため、頂点 $x$ の親を特定するメソッドとして $\mathrm{parent}(x)$ を備えておきます。

頂点 $x$ の親の特定の手続きは以下の通りです。ただし、頂点を移動する際に遅延評価を評価することを忘れないように注意してください。

1. $\mathrm{access}(x)$ する。結果、頂点 $x$ が Splay Tree の根になる。
2. 頂点 $x$ から Splay Tree における左の子頂点に $1$ 回降りる。左の子頂点が存在しなければ親頂点は存在しない ($x$ が根である)。
3. その後、Splay Tree において右に降りることができる限り右に降りる。最終的な現在地が親頂点である。

以下は $\mathrm{parent}(7)$ の様子です。

図 15

辺の追加

動的森なので連結成分が一つとは限りません。ここで満を持して、辺の追加を説明します。

図 16

辺の追加を行うメソッドを以下で定義します。

• $\mathrm{link}(u,v) := $ 頂点 $u$ と頂点 $v$ を辺で繋ぐ。
  • $u$ と $v$ が同じ連結成分に属している状態で呼び出すとエラーとする。
  • 連結成分をマージした後、その連結成分の根は頂点 $u$ であるとする。

手続きは以下の $3$ ステップからなります。

1. $\mathrm{access}(u)$ する。
2. $\mathrm{evert}(v)$ する。
3. 頂点 $v$ から頂点 $u$ に向けて light-edge を追加する。

以下は $\mathrm{link}(12,9)$ の様子です。

図 17 (手続き 1 と手続き 2)

まず $\mathrm{access}(12)$ と $\mathrm{evert}(9)$ を行います。

図 18 (手続き 3)

その後、頂点 $9$ から頂点 $12$ に向けて light-edge を追加します。これは頂点 $9$ に対して、Splay Tree における親頂点を $u$ にする操作です。

その結果、パスの分解の状況は以下の図のようになります。ちゃんと頂点 $12$ と頂点 $9$ がリンクされていることが確認できます。

図 19

なお、左右反転の遅延評価があると見づらいので、例によって遅延評価を全て評価して解消した図で説明します。

図 20

辺の削除

最後に、辺の削除を行うメソッドを以下で定義します。

• $\mathrm{cut}(u,v) := $ 頂点 $u$ と頂点 $v$ を繋ぐ辺を削除する。
  • 頂点 $u$ と頂点 $v$ が辺で繋がれていない状態で呼び出すとエラーとする。
  • 辺の削除後、元の連結成分の根が属さない方の連結成分において、どの頂点が根になるかを保証しない (連結成分の根の取得や $\mathrm{evert}$ が可能なので問題はない)。

手続きは以下の $3$ ステップからなります。

1. 頂点 $u$ と頂点 $v$ で、根から遠い方を $X$ とする。
2. $\mathrm{access}(X)$ する。
3. 頂点 $X$ から出る heavy-edge のうち、左の子頂点に向かう heavy-edge を削除する。

以下は $\mathrm{cut(8,9)}$ の様子です。

図 21

今回は頂点 $8$ の方が深いので、根から頂点 $8$ までのパスを構築します。

図 22

頂点 $8$ からは左に heavy-edge が出ているので、これを完全に無くします。

その結果、パスの分解の状況は以下の図のようになります。ちゃんと頂点 $8$ と頂点 $9$ が分断されていることが確認できます。

図 23

辺の管理について

$\mathrm{cut}$ などで、分断する $2$ つの頂点間に辺が存在するかを判定する必要があります。これを LCT の機能で完備しておくこともできますが、定数倍の大きさを考えると、シンプルに $2$ つの頂点をキーにとるハッシュテーブルなどで管理しておくのが良いと思います。

根やパスの管理について

木の根や Splay Tree の根を勝手に想定するのは危険です。可能ならば、計算を行う前に $\mathrm{access}$ や $\mathrm{evert}$ によって明示的に根が何かを指定するのが好ましいです。

頂点重みについて

パスを Splay Tree で管理しているので、Splay Tree の機能を用いて、パス上の頂点の重みに対して一括で操作を行うことができます。総和、Min/Max、アフィン変換、一律更新など、Splay Tree で可能なら全て可能です。

辺重みについて

頂点拡張で辺重みを持つ頂点を追加することで、頂点重みに帰着させることができます。

計算量

詳しいことを説明しませんが、クエリあたりの計算量は対数時間です。

ソースコード

使い方は後述します。あとコメントの英語が拙いのは気にしないでください。雰囲気がわかればいいのです。

ライセンスは守ってくださいね (このライブラリの冒頭に以下を書くだけで良いです)。

• Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024. Released under the MIT license(https://opensource.org/licenses/mit-license.php)

ライセンスに従わない利用を確認した場合、ライセンスに従わない利用をやめるよう指示するなどの処置を取る場合があります。

#include <unordered_map>
#include <cassert>
#include <vector>
#include <numeric>
#include <iostream>
using namespace std;
/*   
    Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024.
    Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
*/
template<typename T , bool product_target_node = true >
class LinkCutTree{
    private:
    struct SplayNode{
        SplayNode *parent = nullptr;
        SplayNode *left = nullptr;
        SplayNode *right = nullptr;
        T Value;
        T Min,Max,Sum;
        long long id = -1;
        long long SubTreeSize = 1;
        bool is_product_target;
        long long TargetFactorCount = 0;
        private:
        bool copied_instance = false;
        public:
        SplayNode copy(){
            assert(copied_instance == false);
            SplayNode res = *this;
            res.left = nullptr;
            res.right = nullptr;
            res.parent = nullptr;
            res.copied_instance = true;
            return res;
        }
        bool lazy_reverse = false;
        void set_lazyReverse(){this->lazy_reverse = !(this->lazy_reverse);}
        pair<bool,pair<T,T> > lazy_affine ={false , {T(),T()}};
        void set_lazyAffine(T a, T b){
            if(this->lazy_affine.first)this->lazy_affine.second = { a*this->lazy_affine.second.first , a*this->lazy_affine.second.second + b};
            else this->lazy_affine = {true , {a,b}};
        }
        pair<bool,T> lazy_update = {false,T()};
        void set_lazyUpdate(T x){
            this->lazy_update.first = true;
            this->lazy_update.second=x;
            this->lazy_affine.first = false;
        }
        SplayNode(long long id_ ,T val , bool is_product_target_)
            :id(id_) , Value(val), is_product_target(is_product_target_){
            update();
        }
        void rotate(){
            if(this->parent->parent != nullptr){
                if(this->parent == this->parent->parent->left)this->parent->parent->left = this;
                else if(this->parent == this->parent->parent->right)this->parent->parent->right = this;
            }
            this->parent->eval();
            this->eval();
            if(this->parent->left == this){
                this->parent->left = this->right;
                if(this->right != nullptr)this->right->parent = this->parent;
                this->right = this->parent;
                this->parent = this->right->parent;
                this->right->parent = this;
                this->right->update();
            }else{
                this->parent->right = this->left;
                if(this->left != nullptr)this->left->parent = this->parent;
                this->left = this->parent;
                this->parent = this->left->parent;
                this->left->parent = this;
                this->left->update();
            }
            this->update();
            return;
        }
        int state(){
            if(this->parent == nullptr)return 0;
            this->parent->eval();
            if(this->parent->left == this)return 1;
            else if(this->parent->right == this)return 2;
            return 0;
        }
        void splay(){
            while(this->state()!=0){
                if(this->parent->state() == 0){
                    this->rotate();
                    break;
                }
                if( this->parent->state() == this->state() )this->parent->rotate();
                else this->rotate();
                this->rotate();
            }
            this->update();
            return;
        }
        void update(){
            assert(copied_instance == false);
            this->eval();
            this->SubTreeSize = 1;
            this->TargetFactorCount = 0;
            if(this->is_product_target){
                this->Sum = this->Value;
                this->Min = this->Value;
                this->Max = this->Value;
                this->TargetFactorCount++;
            }else{
                this->Sum = 0;
                this->Min = numeric_limits<T>::max();
                this->Max = numeric_limits<T>::min();
            }
            if(this->left != nullptr){
                this->left->eval();
                this->SubTreeSize += this->left->SubTreeSize;
                this->TargetFactorCount += this->left->TargetFactorCount;
                if(this->left->Min < this->Min)this->Min = this->left->Min;
                if(this->left->Max > this->Max)this->Max = this->left->Max;
                this->Sum += this->left->Sum;
            }
            if(this->right != nullptr){
                this->right->eval();
                this->SubTreeSize += this->right->SubTreeSize;
                this->TargetFactorCount += this->right->TargetFactorCount;
                if(this->right->Min < this->Min)this->Min = this->right->Min;
                if(this->right->Max > this->Max)this->Max = this->right->Max;
                this->Sum += this->right->Sum;
            }
            return;
        }
        void eval(){
            assert(copied_instance == false);
            if(this->lazy_reverse){
                swap(this->left , this->right);
                if(this->left != nullptr)this->left->set_lazyReverse();
                if(this->right != nullptr)this->right->set_lazyReverse();
                this->lazy_reverse = false;
            }
            if(this->TargetFactorCount == 0){
                this->lazy_update.first = false;
                this->lazy_affine.first = false;
                return;
            }
            if(this->lazy_update.first){
                if(this->is_product_target){
                    this->Value = this->Min = this->Max = this->lazy_update.second;
                }
                this->Sum = (this->lazy_update.second)*(this->TargetFactorCount);
                if(this->left != nullptr)this->left->set_lazyUpdate(this->lazy_update.second);
                if(this->right != nullptr)this->right->set_lazyUpdate(this->lazy_update.second);
                this->lazy_update.first = false;
            }
            if(this->lazy_affine.first){
                if(this->is_product_target){
                    this->Value = this->lazy_affine.second.first * this->Value + this->lazy_affine.second.second;
                }
                this->Min = this->lazy_affine.second.first * this->Min + this->lazy_affine.second.second;
                this->Max = this->lazy_affine.second.first * this->Max + this->lazy_affine.second.second;
                this->Sum = this->lazy_affine.second.first * this->Sum + this->TargetFactorCount*this->lazy_affine.second.second;
                if(this->Max < this->Min)swap(this->Max,this->Min);
                if(this->left != nullptr)this->left->set_lazyAffine(this->lazy_affine.second.first,this->lazy_affine.second.second);
                if(this->right != nullptr)this->right->set_lazyAffine(this->lazy_affine.second.first,this->lazy_affine.second.second);
                this->lazy_affine.first = false;
            }
        }
    };
    private:
    int m_N;
    vector<SplayNode*> m_Nodes;
    vector<unordered_map<long long,SplayNode*>> m_Edges;
    vector<unordered_map<long long,bool>> m_ExistEdge;
    T init_v;
    SplayNode* get_sub(long long index , SplayNode* root){
        if(root==nullptr)return root;
        SplayNode* now = root;
        while(true){
            now->eval();
            long long left_size = 0;
            if(now->left != nullptr)left_size = now->left->SubTreeSize;
            if(index < left_size)now = now->left;
            else if(index > left_size){
                now = now->right;
                index -= left_size+1;
            }else break;
        }
        now->splay();
        return now;
    }
    void init(){
        m_Nodes.clear();
        m_ExistEdge.clear();
        m_Edges.clear();
        for(int i = 0 ; i < m_N ; i++)m_Nodes.push_back(new SplayNode(i,init_v,product_target_node));
        m_ExistEdge = vector<unordered_map<long long,bool>>(m_N);
        if(!product_target_node)m_Edges = vector<unordered_map<long long,SplayNode*>>(m_N);
    }
    void release(){
        for(SplayNode* p : m_Nodes){
            if(p != nullptr)delete p;
        }
    }
    public:
    LinkCutTree():init_v(T(0)){init();}
    LinkCutTree(int n, T init_v_ = T(0)):m_N(n),init_v(init_v_){init();}
    ~LinkCutTree(){release();}
    LinkCutTree(const LinkCutTree &x) = delete ;
    LinkCutTree& operator = (const LinkCutTree &x) = delete ;
    LinkCutTree (LinkCutTree&& x){assert(0);}
    LinkCutTree& operator = ( LinkCutTree&& x){assert(0);}
    long long access(const long long id){
        assert(0 <= id && id < m_N);
        if(m_Nodes[id] == nullptr)return -1;
        long long res = id;
        while(1){
            m_Nodes[id]->splay();
            m_Nodes[id]->right = nullptr;
            m_Nodes[id]->update();
            if(m_Nodes[id]->parent == nullptr)break;
            res = m_Nodes[id]->parent->id;
            m_Nodes[id]->parent->splay();
            m_Nodes[id]->parent->right = m_Nodes[id];
            m_Nodes[id]->parent->update();
        }
        return res;
    }
    long long path_xth_element(long long v , int x){
        assert(0 <= v && v < m_N);
        assert(0 <= x && x <= depth(v));
        access(v);
        SplayNode* nd;
        if(product_target_node)nd = get_sub(x , m_Nodes[v]);
        else nd = nd = get_sub(x*2 , m_Nodes[v]);
        access(v);
        return nd->id;
    }
    long long root(long long x){
        assert(0 <= x && x < m_N);
        return path_xth_element(x,0);
    }
    bool same(long long u , long long v){
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        return bool(root(u) == root(v));
    }
    long long depth(long long x){
        assert(0 <= x && x < m_N);
        access(x);
        if(product_target_node)return m_Nodes[x]->SubTreeSize - 1;
        return (m_Nodes[x]->SubTreeSize - 1)>>1;
    }
    long long parent(long long x){
        assert(0 <= x && x < m_N);
        if(this->depth(x) == 0)return -1;
        return this->path_xth_element(x , this->depth(x)-1);
    }
    void evert(long long x){
        assert(0 <= x && x < m_N);
        access(x);
        m_Nodes[x]->set_lazyReverse();
        m_Nodes[x]->update();
        access(x);
    }
    void link(long long u , long long v){
        assert(product_target_node);
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        assert(!same(u,v));
        evert(v);
        access(v);
        access(u);
        m_ExistEdge[u][v] = true;
        m_ExistEdge[v][u] = true;
        m_Nodes[v]->parent = m_Nodes[u];
        m_Nodes[u]->update();
    }
    void link(long long u , long long v , T w){
        assert(!product_target_node);
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        assert(!same(u,v));
        m_ExistEdge[u][v] = true;
        m_ExistEdge[v][u] = true;
        SplayNode* edge_factor = new SplayNode(-1,w,true);
        m_Edges[u][v] = edge_factor;
        m_Edges[v][u] = edge_factor;
        evert(v);
        access(v);
        access(u);
        m_Nodes[v]->parent = edge_factor;
        edge_factor->parent = m_Nodes[u];
        m_Nodes[u]->update();
    }
    void cut(long long u , long long v){
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        assert(m_ExistEdge[u][v] && m_ExistEdge[v][u]);
        m_ExistEdge[u][v] = false;
        m_ExistEdge[v][u] = false;
        if(depth(u) > depth(v))swap(u,v);
        access(v);
        if(product_target_node == false){
            m_Edges[u][v]->splay();
            m_Edges[u][v]->left->parent = nullptr;
            m_Edges[u][v]->left = nullptr;
            m_Edges[u][v]->update();
            m_Edges[u][v] = nullptr;
            m_Edges[v][u] = nullptr;
        }
        m_Nodes[v]->splay();
        m_Nodes[v]->left->parent = nullptr;
        m_Nodes[v]->left = nullptr;
        m_Nodes[v]->update();
        if(product_target_node == false)delete m_Edges[v][u];
    }
    void update_val(long long i , T x){
        assert(0 <= i && i < m_N);
        assert(product_target_node);
        access(i);
        m_Nodes[i]->Value = x;
        m_Nodes[i]->update();
    }
    void update_val(long long u , long long v , T w){
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        assert(product_target_node == false);
        assert(m_ExistEdge[u][v]);
        SplayNode* edge_factor = m_Edges[u][v];
        edge_factor->splay();
        edge_factor->Value = w;
        edge_factor->update();
    }
    void PathUpdate(long long i , T x){
        assert(0 <= i && i < m_N);
        access(i);
        m_Nodes[i]->set_lazyUpdate(x);
        m_Nodes[i]->update();
        access(i);
    }
    void PathAffine(long long i , T A , T B){
        assert(0 <= i && i < m_N);
        access(i);
        m_Nodes[i]->set_lazyAffine(A,B);
        m_Nodes[i]->update();
        access(i);
    }
    void PathAdd(long long i , T x){PathAffine(i,T(1),x);}
    long long LCA(long long x , long long y){
        assert(0 <= x && x < m_N);
        assert(0 <= y && y < m_N);
        assert(same(x,y));
        if(root(x) != root(y))return -1;
        else {
            access(x);
            long long lca = access(y);
            access(lca);
            return lca;
        }
    }
    SplayNode operator [](long long nodeID){
        access(nodeID);
        return m_Nodes[nodeID]->copy();
    }
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
};

使用例

void usage_LCT(){
    /*
        ~~~~~~~~~~~~~~~~~~~~~
        頂点重みを持つ場合の使用法
        ~~~~~~~~~~~~~~~~~~~~~
    */
    // 頂点重みならテンプレートの第二引数が true
    LinkCutTree<int , true> V(10,0);// 頂点数と重みの初期値

    // 初期状態では辺が一つもない

    // 辺を追加
    V.link(0,1);
    V.link(0,2);
    V.link(1,3);
    V.link(1,5);
    V.link(2,4);

    // 必ずしも連結になる必要はない
    V.link(8,6);
    V.link(7,6);
    V.link(8,9);


    // 頂点重みの変更
    V.update_val(0,4);
    V.update_val(1,-5);
    V.update_val(3,2);
    V.update_val(4,-2);


    // V.link(0,3); -> すでに同じ連結成分の頂点を link するとエラー 

    // クエリの前に、evert(x) で頂点 x の属する木の根を指定すると安全
    V.evert(0);

    // [x] でアクセスすると、頂点 x が属する木の根から頂点 x までのパスを
    // 表現する Splay Tree の木の根のコピーが返ってくる。ここでパスの重み Sum,Min などを取得できる
    // なお返ってくる Splay Tree のノードは、内部的には頂点 x を表現するものでもある。
    std::cerr 
        << V[3].Sum << " , "
        << V[3].Min << " , "
        << V[3].Max 
    << std::endl;// 1 , -5 , 4


    // 根を頂点 1 に変更
    V.evert(1);

    // 根から頂点 4 へのパス長
    std::cerr << V.depth(4) << std::endl;// 3

    // 根から頂点 4 までのパス上で、2 番目の頂点番号を返す
    std::cerr << V.path_xth_element(4,2) << std::endl;// 2

    // ある頂点に対して、属する木の根や親頂点の取得も可能
    std::cerr << V.parent(4) << std::endl;// 2
    std::cerr << V.root(4) << std::endl;// 1

    // 辺 (1-3) を削除
    V.cut(1,3);

    // 辺を追加
    V.link(0,9);

    // 根を頂点 0 に変更 (都度、明示的に設定すると安全)
    V.evert(0);

    // 根から頂点 7 までのパス上の頂点重みを全て 3 に変更
    V.PathUpdate(7,3);

    // 頂点 7 から 1 までのパス上の頂点重み和
    V.evert(7);
    std::cerr << V[1].Sum << std::endl;// 10


    // 根から頂点 4 までのパス上の頂点重み全てを 2 倍してから -4 する
    V.PathAffine(4,2,-4);

    // 頂点 4 から 8 までのパス上の頂点重みの Min
    V.evert(4);
    std::cerr << V[8].Min << std::endl;// -8 

    /*
        ~~~~~~~~~~~~~~~~~~~~
        辺重みを持つ場合の使用法
        ~~~~~~~~~~~~~~~~~~~~
    */
    // 辺重みならテンプレートの第二引数が false
    LinkCutTree<int , false> E(10);// 頂点重みの初期値は無意味。省略可能

    // 辺追加時に重みを指定しなければエラーになる
    E.link(0,1,1);
    E.link(1,2,-4);
    E.link(3,2,2);
    E.link(3,4,-5);
    E.link(1,5,1);
    E.link(5,6,15);

    // 辺の重み変更はこうする！
    E.update_val(1,5,2);

    // 辺重みを持つ場合、PathUpdate などの対象が辺重みになる
    E.evert(0);
    E.PathUpdate(4,-100);

    E.link(4,9,-2);
    E.evert(0);

    // パスを表す Splay Tree も、パス上の辺重みについての集約をもつようになる
    std::cout << E[9].Sum << std::endl;// -402
}

機能 & 仕様

動的な木を明示的に管理するのではなく、木上のパスを SplayTree (列型) として管理する。

• 頂点重みをもつか、辺重みを持つかを、テンプレートパラメータ product_target_node で指定

  • true -> 頂点重み
  • false -> 辺重み

• evert(x) := xを連結成分のrootに

• link(x,y) := x,y に辺を追加 (元々 x,y は非連結)

  • 頂点重みの場合限定

• link(x,y) := x,y に重み w の辺を追加 (元々 x,y は非連結)

  • 辺重みの場合限定

• cut(x,y) := x,y から辺を削除 (元々 x,y に辺がある)

• access(x) := x の属する木の根から x までを HeavyEdge で繋ぎ、パスにする。

  • パスは SplayTree である。
  • ついでに m_Nodes[x] を SplayTree の根にする (splay)
  • access(x)で繋がった SplayTreeは、左の方が根に近く、右に行くほど下の頂点になる (path である)

• 根から x までの path の情報 (重みの Sum など) は、access(x) してから m_Nodes[x]->Sum などで取得できる

  • 頂点重みを集約するか、辺重みを集約するかは、テンプレートパラメータで指定する

• operator [x] := 頂点 x に対応する SplayNode のコピー (隣接 SplayNode へのポインタを封印してある)

  • にアクセスすると自動で access(x) される。
  • つまり、[x] は 「根から x までのパスを表す SplayTree の根」(のコピー) を取得する

• root(x) := x の属する木の根

• depth(x) := x の深さ

• same(x,y) := x,y が同じ木に属しているか

• parent(x) := x の親頂点の番号。なければ -1 を返す。

• LCA(x,y) := x,y の lca (x,y は同じ木に属する)

• path_xth_element(v,x) := v の属する木の「根から頂点 v までのパス」上で深さが x の頂点番号

• 重みの更新。重みを持つ対象 (頂点 or 辺) を product_target と呼ぶことにする

  • update_val(i,x) := 頂点 i の重みを x にする
    • 頂点重みの場合 (product_target が頂点の場合) 限定
  • update_val(u,v,w) := 辺 (u,v) の重みを w にする
    • 辺重みの場合 (product_target が辺の場合) 限定
  • PathUpdate(i,x) := 属する木の根から頂点 i までのパス上の product_target の重みを一律 x に更新する
  • PathAffine(i,A,B) := 属する木の根から頂点 i までのパス上の product_target の重み (Value) を一律 A*Value + B に更新
  • PathUpdate(i,x) := 属する木の根から頂点 i までのパス上の　product_target　の重みに一律 x 加算する

• 内部的には、辺重みを持つ場合の辺要素を、頂点拡張した頂点として管理している。

  • product_target ではない方の Value を無視する

いかがでしたか

いかがでしたか