Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@NokonoKotlin(おこ ていゆ)

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

Last updated at Posted at 2024-11-24

まえがき

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

リンク-カット木とは

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

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

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

また、この記事を読むための前提として Splay Tree を $30$% ぐらい理解しているといいと思います。


説明

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

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


森の構築

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

図 1

LinkCutTree.001.jpeg

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

図 2

LinkCutTree.002.jpeg

この例では、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

LinkCutTree.003.jpeg

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

図 4

LinkCutTree.004.jpeg

そして、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 を完了させます。

LinkCutTree.005.jpeg


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

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

LinkCutTree.006.jpeg


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

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

LinkCutTree.007.jpeg


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

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

LinkCutTree.008.jpeg


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

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

LinkCutTree.009.jpeg


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

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

LinkCutTree.010.jpeg

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


図 11

LinkCutTree.011.jpeg

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 と同じ図

LinkCutTree.011.jpeg

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


図 12

LinkCutTree.012.jpeg

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

図 13

LinkCutTree.013.jpeg


補足 2

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

図 14

LinkCutTree.014.jpeg


親頂点の特定

連結成分の根の特定と同様の手法で可能ですが、紹介するアルゴリズムのバリエーションのため、頂点 $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

LinkCutTree.015.jpeg

辺の追加

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


図 16

LinkCutTree.016.jpeg

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

  • $\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)$ を行います。

LinkCutTree.017.jpeg


図 18 (手続き 3)

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

LinkCutTree.018.jpeg

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


図 19

LinkCutTree.019.jpeg

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


図 20

LinkCutTree.020.jpeg


辺の削除

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

  • $\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$ までのパスを構築します。

LinkCutTree.021.jpeg


図 22

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

LinkCutTree.022.jpeg

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


図 23

LinkCutTree.023.jpeg


辺の管理について

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


根やパスの管理について

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


頂点重みについて

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


辺重みについて

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


計算量

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


ソースコード

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

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

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

#include<vector>
#include<cassert>
#include<unordered_map>
using namespace std;


/*   
    このコメントは消さないでください。
    Don't remove this comment!!!

    Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024. 
    Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
*/
template<typename T>
class LinkCutTree{
    private:
    
    struct SplayNode{
        SplayNode *parent = nullptr;
        SplayNode *left = nullptr;
        SplayNode *right = nullptr;
        
        // value of this node
        T Value;

        // Monoid product of subtree
        T Min,Max,Sum;

        // number of this node
        long long id = -1;

        // size of subtree
        long long SubTreeSize = 1;// SplayTree の部分木サイズ

        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 reverse_flag_lazy = false;
        void set_lazyReverse(){this->reverse_flag_lazy = !(this->reverse_flag_lazy);}
        
        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){
            id = id_;
            Value = val;
            Min = val;
            Max = val;
            Sum = val;
            update();
        }
        
        void rotate(){
            if(this->parent->parent){
                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)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)this->left->parent = this->parent;
                this->left = this->parent;
                this->parent = this->left->parent;
                this->left->parent = this;
                this->left->update();
            }

            this->update();
            return;
        }
        /*
            direction of parent
            0 -> no parent or connected by light-edge
            else 1 or 2 (detail of direction is not so important)
        */
        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;
        }

        // サイズなど、Nodeの持っている情報をupdateする(順番大事)
        void update(){
            assert(copied_instance == false);
            
            this->eval();
            this->SubTreeSize = 1;
            this->Min = this->Value;
            this->Max = this->Value;
            this->Sum = this->Value;
            if(bool(this->left)){
                this->left->eval();
                this->SubTreeSize += this->left->SubTreeSize;
                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(bool(this->right)){
                this->right->eval();
                this->SubTreeSize += this->right->SubTreeSize;
                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->reverse_flag_lazy){
                swap(this->left , this->right);
                if(bool(this->left))this->left->set_lazyReverse();
                if(bool(this->right))this->right->set_lazyReverse();
                this->reverse_flag_lazy = false;
            }

            if(this->lazy_update.first){
                this->Value = this->Min = this->Max = this->lazy_update.second;
                this->Sum = (this->lazy_update.second)*(this->SubTreeSize);
                if(bool(this->left))this->left->set_lazyUpdate(this->lazy_update.second);
                if(bool(this->right))this->right->set_lazyUpdate(this->lazy_update.second);
                this->lazy_update.first = false; 
            }
            if(this->lazy_affine.first){
                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->SubTreeSize*this->lazy_affine.second.second;
                if(bool(this->left))this->left->set_lazyAffine(this->lazy_affine.second.first,this->lazy_affine.second.second);
                if(bool(this->right))this->right->set_lazyAffine(this->lazy_affine.second.first,this->lazy_affine.second.second);
                this->lazy_affine.first = false; 
            }
        }

        SplayNode* _before(){
            SplayNode* res = this;
            res->splay();
            res->eval();
            if(res->left == nullptr)return nullptr;
            res = res->left;
            res->eval();
            while(res->right != nullptr){
                res = res->right;
                res->eval();
            }
            res->splay();
            return res;
        }
    };

    private:

    int m_N;
    // m_Nodes[i] := pointer of vertex i
    vector<SplayNode*> m_Nodes;
    
    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();
        for(int i = 0 ; i < m_N ; i++)m_Nodes.push_back(new SplayNode(i,init_v));

        m_ExistEdge = vector<unordered_map<long long,bool>>(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)):init_v(init_v_),m_N(n){init();}
    // Don' copy this object
    LinkCutTree(const LinkCutTree<T> &x) = delete ;
    LinkCutTree<T>& operator = (const LinkCutTree<T> &x) = delete ;
    // Don' move this object
    LinkCutTree (LinkCutTree<T>&& x){assert(0);}
    LinkCutTree<T>& operator = ( LinkCutTree<T>&& x){assert(0);}
    
    // construct a path from root to [id]
    long long access(const long long id){
        assert(0 <= id && id < m_N);
        if(bool(m_Nodes[id]) == false)return -1;
        long long res = id;
        while(1){
            m_Nodes[id]->splay();
            m_Nodes[id]->right = nullptr;
            m_Nodes[id]->update();
            if(bool(m_Nodes[id]->parent) == false)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 = get_sub(x , 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);
        return m_Nodes[x]->SubTreeSize - 1;
    }

    pair<bool,long long> parent(long long x){
        assert(0 <= x && x < m_N);
        pair<bool,long long> res;
        access(x);
        SplayNode* p = m_Nodes[x]->_before();
        if(p == nullptr)res.first = false;
        else {
            res.first = true;
            res.second = p->id;
        }
        return res;
    }

    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(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();
    }

    bool 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);

        m_Nodes[v]->left->parent = nullptr;
        m_Nodes[v]->left = nullptr;
        m_Nodes[v]->update();
        return true;
    }

    void update_val(long long i , T x){
        assert(0 <= i && i < m_N);
        access(i);
        m_Nodes[i]->Value = x;
        m_Nodes[i]->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;
        }
    }
    // get the copy object of node [nodeID]
    SplayNode operator [](long long nodeID){
        access(nodeID);
        return m_Nodes[nodeID]->copy();
    }
};





int main(){
    LinkCutTree<int> T(5,0);
    return 0;
}

機能 & 仕様

  • access と evert

    • access(x) := 頂点 $x$ の属する木の根から $x$ までを heavy-edge で繋いでパスにする。
      • 頂点 $x$ を SplayTree の根にし、パスのデータを頂点 $x$ からアクセス可能にする。
      • 頂点 $x$ を、根から頂点 $x$ までのデータ取得のインターフェースにする役割。
    • evert(x) := 頂点 $x$ の属する木の根を $x$ に変更する。
      • ついでに access(x) が実行される。
      • 連結成分の根が何かを保証する

  • 基本機能

    • link(x,y) := 頂点 $x,y$ に辺を追加 (元々 $x,y$ は非連結である必要がある)
      • 連結後の連結成分の根は $x$ である。
    • cut(x,y) := 頂点 $x,y$ を繋ぐ辺を削除 (元々 $x,y$ に辺がある必要がある)
      • 削除後、元の連結成分の根が属さない方の連結成分の根が何になるかを保証しない。
      • 適宜 evert などをしてください。
    • [x] := 「根から $x$ までのパスを表す SplayTree の根」(のコピー) を取得する
      • 隣接する SplayNode へのポインタを封印してある。
      • 自動で access(x) される。
    • update_val(i,x) := 頂点 $i$ の重み (Value) を $x$ にする。
    • root(x) := 頂点 $x$ の属する木の根
    • depth(x) := 頂点 $x$ の深さ
    • same(x,y) := 頂点 $x,y$ が同じ木に属しているか
    • parent(x) := (頂点 $x$ の親が存在するか, 親の番号) のペア
    • LCA(x,y) := 頂点 $x,y$ の LCA ( $x,y$ は同じ木に属する必要がある )

  • パスに関する機能

    • path_xth_element(v,x) := 頂点 $v$ の属する木の「根から頂点 $v$ までのパス」のうち 深さが $x$ の頂点番号
    • PathUpdate(i,x) := 頂点 $i$ が属する木の根から頂点 $i$ までのパス上の頂点重み
      を (Value) 一律 $x$ に更新する
    • PathAffine(i,A,B) := 頂点 i が属する木の根から頂点 $i$ までのパス上の頂点重み
      (Value) を一律 $A\times\mathrm{Value} + B$ に更新

いかがでしたか

いかがでしたか

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?