まえがき

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

はじめに

Euler Tour Tree (以降、ETT とします) は根付きの 動的木 ないしは 動的森 を管理するデータ構造です。この記事を読む前に平衡二分木と Link-Cut Tree について学んでいると良いです。

図 1

Link-Cut Tree もまた動的森を管理するデータ構造ですが、Link-Cut Tree ではパスに関するデータ取得がメインでした。ETT では、木の DFS 順のデータを取得できます。

また、Link-Cut Tree と組み合わせることで木の 部分木 に対するデータ取得も可能になります。

データ構造

概要

オイラーツアー列を以下で定義します。

木の根からの DFS を行い、通った辺と頂点を記録した列。
辺は通った順に記録する。
頂点を通るタイミングは何度か存在するので、そのうちいずれか一度のみを記録する。

ETT は動的森の各連結成分についてオイラーツアー列を管理するデータ構造です。

図 2

例えば図 2 は各連結成分の DFS の道順の $1$ つを示しています。この道順に対して、オイラーツアー列のひとつを示したのが以下の図です。

図 3

ここで、改めてオイラーツアー列の構造について補足しておきます。図において、丸枠の要素が頂点に対応しており、長方形の要素が辺に対応しています。便宜上、頂点に対応する要素を頂点要素、辺に対応する要素を辺要素と呼ぶことにします。

図 3 においては、頂点要素は初めて頂点に到達するのと同じタイミングでオイラーツアー列に登場していますが、これはたまたまそうなっているだけです。ここでのオイラーツアー列の定義では、頂点要素の登場箇所については強く保証されていないことに注意しておいてください。

オイラーツアー列は順序を持つので、これを平衡二分木で管理することにします。

図 4

ETT では、森ないし森における操作をここで定義したオイラーツアー列で表現することで、DFS 順のデータを管理します。

また実装においては、平衡二分木とは別でオイラーツアー列の要素を指すポインタを以下のデータ構造で管理しておきます。

$\mathrm{NodeFactor}[x] := $ 頂点 $x$ に対応する頂点要素を指すポインタ
$\mathrm{EdgeFactor}[u][v] := $ 頂点 $u$ から頂点 $v$ への有向辺に対応する辺要素を指すポインタ

これらは配列とハッシュテーブルを組み合わせることで十分高速に管理できます。

連結成分の根の変更

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

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

図 5

連結成分の根を変更する手続きは、根にしたい頂点が属する連結成分のオイラーツアー列の順番を入れ替えることで実行可能です。具体的には、$\mathrm{evert}(x)$ では以下の手続きを行います。

頂点 $x$ に対応する頂点要素が、オイラーツアー列において何番目の要素かを特定する。これは平衡二分木の機能で実行可能。
頂点 $x$ に対応する頂点要素の直前でオイラーツアー列を二分し、それらを元と反対の順で結合する。

以下の図は、頂点 $6$ が属する連結成分の根を頂点 $6$ にする操作の様子です。

図 6

得られた列もちゃんと頂点 $6$ からのオイラーツアー列のひとつであることが確認できます。

辺の追加

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

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

図 7

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

頂点 $u$ と $v$ を $\mathrm{evert}$ する。
以下を順に連結してひとつのオイラーツアー列にする。

頂点 $u$ からのオイラーツアー列
頂点 $u$ から頂点 $v$ への辺要素 (新たに生成)
頂点 $v$ からのオイラーツアー列
頂点 $v$ から頂点 $u$ への辺要素 (新たに生成)

図 8

図を確認すると、頂点 $u$ を根とするオイラーツアー列になっていることが確認できます。

辺の削除

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

$\mathrm{cut}(u,v) := $ 頂点 $u$ と頂点 $v$ を繋ぐ辺を削除する。
- 頂点 $u$ と頂点 $v$ が辺で繋がれていない状態で呼び出すとエラーとする。

図 9

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

頂点 $u$ を $\mathrm{evert}$ する。
頂点 $u$ からのオイラーツアー列を、$2$ つの辺要素 $(u \rightarrow v)$ , $(v \rightarrow u)$ の登場地点で $\mathrm{split}$ し、辺要素 $(u \rightarrow v)$ , $(v \rightarrow u)$ は削除する。
手続き $2$ の $\mathrm{split}$ で得た $3$ つの列を左から順に $A,B,C$ とし、頂点 $u$ からのオイラーツアー列を $A$ と $C$ をこの順に連結したもの、頂点 $v$ からのオイラーツアー列を $B$ とする。

図 10

手続きの図を確認すると、それぞれオイラーツアー列になっていることが確認できます。

図 11

データの更新/取得

根の取得

頂点 $x$ が属する連結成分の根はオイラーツアーの開始点なので、頂点 $x$ からのオイラーツアー列の最左の要素をみることで特定することができます。頂点 $x$ に対応する頂点要素のポインタを $\mathrm{NodeFactor}[x]$ で管理しているので、その頂点から平衡二分木の根まで移動し、その後左に降り続けることで列の最左に到達することができます。

また、二つの頂点に対して、連結成分の根が一致するかをみることで、同じ連結成分に属するかの判定も可能です。

部分木

オイラーツアー列は平衡二分木で表現されているので、区間に対して集約の計算や遅延評価による更新を行うことができます。

オイラーツアー列からうまく区間を選択すると、元の木における部分木と対応する区間を得ることができます。もし頂点 $x$ の親頂点 $p$ がわかっているなら、$2$ つの辺要素 $(p\rightarrow x)$ と $(x\rightarrow p)$ の間の要素を選ぶことで、頂点 $x$ の部分木に対応する区間を得ることができます。

ETT で親頂点を特定することは難しいので、Link-Cut Tree で親を特定してから操作を行うと良いです。なお、親がない場合、すなわち $x$ が根頂点の場合、部分木は木全体のことなので、オイラーツアー全体を見れば良いです。

図 12

オイラーツアーの頂点要素には頂点重みを、辺要素には辺重みを持たせることにしましょう。先述で得た区間内に登場する頂点要素も辺要素も、頂点 $x$ の部分木に含まれるものなので、この区間に対して区間の操作を行うことで部分木に対する操作を行うことができます。

実際に区間操作を行う際、頂点要素と辺要素を分けて考える必要があることに注意してください。具体的には、頂点要素に対する集約の計算や遅延評価の際は辺要素を見ないようにし、辺要素に対する集約の計算や遅延評価の際は頂点要素を見ないように実装してください。

ソースコード

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

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

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

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

#include <unordered_map>
#include <cassert>
#include <queue>
#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 EulerTourTree{
    private:
    struct SplayNode{
        SplayNode *parent = nullptr;
        SplayNode *left = nullptr;
        SplayNode *right = nullptr;
        T Value;
        T Min,Max,Sum;
        long long SubTreeSize = 1;
        bool is_product_target;
        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;
        }
        long long from , to;
        bool isNodeFactor = false;
        long long TargetFactorCount = 0;
        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(){}
        SplayNode(long long from_, long long to_, T val , bool is_product_target_)
            :from(from_),to(to_),Value(val),is_product_target(is_product_target_){
            this->update();
        }
        void rotate(){
            if(this->parent->parent != nullptr){
                if(this->parent == this->parent->parent->left)this->parent->parent->left = this;
                else 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->parent != nullptr){
                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->left != nullptr){
                this->left->eval();
                this->SubTreeSize += this->left->SubTreeSize;
                this->TargetFactorCount += this->left->TargetFactorCount;
            }
            if(this->right != nullptr){
                this->right->eval();
                this->SubTreeSize += this->right->SubTreeSize;
                this->TargetFactorCount += this->right->TargetFactorCount;
            }
            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->TargetFactorCount == 0)return;
            if(this->left != nullptr){
                this->left->eval();
                this->Min = min<T>(this->left->Min,this->Min);
                this->Max = max<T>(this->left->Max,this->Max);
                this->Sum += this->left->Sum;
            }
            if(this->right != nullptr){
                this->right->eval();
                this->Min = min<T>(this->right->Min,this->Min);
                this->Max = max<T>(this->right->Max,this->Max);
                this->Sum += this->right->Sum;
            }
            return;
        }
        void eval(){
            assert(copied_instance == 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->lazy_update.second;
                }
                this->Min = this->lazy_update.second;
                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;
            }
        }
        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;
        }
    };
    SplayNode *get_sub(int index , SplayNode *root){
        if(root==nullptr)return root;
        SplayNode *now = root;
        while(true){
            now->eval();
            int 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;
    }
    SplayNode *merge(SplayNode *leftRoot , SplayNode *rightRoot){
        if(leftRoot!=nullptr)leftRoot->update();
        if(rightRoot!=nullptr)rightRoot->update();
        if(leftRoot == nullptr)return rightRoot;
        if(rightRoot == nullptr)return leftRoot;
        rightRoot = get_sub(0,rightRoot);
        rightRoot->left = leftRoot;
        leftRoot->parent = rightRoot;
        rightRoot->update();
        return rightRoot;
    }
    std::pair<SplayNode*,SplayNode*> split(int leftnum, SplayNode *root){
        if(leftnum<=0)return std::make_pair(nullptr , root);
        if(leftnum >= root->SubTreeSize)return std::make_pair(root, nullptr);
        root = get_sub(leftnum , root);
        SplayNode *leftRoot = root->left;
        SplayNode *rightRoot = root;
        if(rightRoot != nullptr)rightRoot->left = nullptr;
        if(leftRoot != nullptr)leftRoot->parent = nullptr;
        leftRoot->update();
        rightRoot->update();
        return std::make_pair(leftRoot,rightRoot);
    }
    int m_N;
    vector<SplayNode*> m_NodeFactor;
    vector<unordered_map<long long,SplayNode*>> m_EdgeFactor;
    T init_v;
    long long find_NodeFactor(long long u){
        assert(0 <= u && u < m_N);
        m_NodeFactor[u]->splay();
        if(m_NodeFactor[u]->left != nullptr)return m_NodeFactor[u]->left->SubTreeSize;
        return 0;
    }
    long long find_EdgeFactor(long long u , long long v){
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        if(m_EdgeFactor[u][v] == nullptr)return -1;
        m_EdgeFactor[u][v]->splay();
        if(m_EdgeFactor[u][v]->left != nullptr)return m_EdgeFactor[u][v]->left->SubTreeSize;
        return 0;
    }
    pair<SplayNode*,pair<SplayNode*,SplayNode*>> SplitSubTree(long long u , long long p){
        assert(0 <= u && u < m_N);
        assert(0 <= p && p < m_N);
        long long rt = root(u);
        if(u == rt){
            m_NodeFactor[u]->splay();
            return {m_NodeFactor[u],{nullptr,nullptr}};
        }
        assert(m_EdgeFactor[p][u] != nullptr);
        long long l = find_EdgeFactor(p,u);
        long long r = find_EdgeFactor(u,p);
        assert(l < r);
        m_NodeFactor[u]->splay();
        pair<SplayNode*,SplayNode*> tmp = split(r,m_NodeFactor[u]);
        SplayNode* rightnode = tmp.second;
        tmp = split(l+1,tmp.first);
        return {tmp.second,{tmp.first,rightnode}};
    }
    void init(){
        m_NodeFactor.clear();
        m_EdgeFactor.clear();
        for(int i = 0 ; i < m_N ; i++){
            m_NodeFactor.push_back(new SplayNode(i,i,init_v,product_target_node));
        }
        m_EdgeFactor.resize(m_N);
    }
    void release(){
        for(SplayNode* p : m_NodeFactor)if(p != nullptr)delete p;
        for(unordered_map<long long,SplayNode*> table : m_EdgeFactor){
            for(pair<long long,SplayNode*>e : table)if(e.second != nullptr)delete e.second;
        }
    }
    public:
    EulerTourTree():init_v(T()){}
    EulerTourTree(int n ,T init_v_ = T(0)):init_v(init_v_),m_N(n){
        init();
    }
    ~EulerTourTree(){release();}
    EulerTourTree(const EulerTourTree<T> &x) = delete ;
    EulerTourTree<T> & operator = (const EulerTourTree<T> &x) = delete ;
    EulerTourTree ( EulerTourTree<T> && x){assert(0);}
    EulerTourTree<T> & operator = ( EulerTourTree<T> && x){assert(0);}
    bool exist_edge(long long u, long long v){
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        return bool(m_EdgeFactor[u][v] != nullptr && m_EdgeFactor[v][u] != nullptr);
    }
    void update_val(long long i , T x){
        assert(0 <= i && i < m_N);
        assert(product_target_node);
        m_NodeFactor[i]->splay();
        assert(m_NodeFactor[i]->is_product_target);
        m_NodeFactor[i]->Value = x;
        m_NodeFactor[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(exist_edge(u,v));
        SplayNode* e1 = m_EdgeFactor[u][v];
        SplayNode* e2 = m_EdgeFactor[v][u];
        if(e2->is_product_target)swap(e1,e2);
        assert(e1->is_product_target);
        e1->splay();
        e1->Value = w;
        e1->update();
    }
    long long EulerTourSize(long long r){
        assert(0 <= r && r < m_N);
        evert(r);
        m_NodeFactor[r]->splay();
        return m_NodeFactor[r]->SubTreeSize;
    }
    long long ComponentSize(long long u){
        assert(0 <= u && u < m_N);
        return (EulerTourSize(u) + 2)/3;
    }
    long long root(long long u){
        assert(0 <= u && u < m_N);
        SplayNode* tmp = m_NodeFactor[u];
        tmp->splay();
        tmp->eval();
        while(tmp->left != nullptr){
            tmp = tmp->left;
            tmp->eval();
        }
        tmp->splay();
        return tmp->from;
    }
    bool same(long long u ,long long v){return bool(root(u) == root(v));}
    void evert(long long u){
        assert(0 <= u && u < m_N);
        if(root(u) == u)return;
        long long c = find_NodeFactor(u);
        m_NodeFactor[u]->splay();
        pair<SplayNode*,SplayNode*> tmp = split(c,m_NodeFactor[u]);
        merge(tmp.second,tmp.first);
        m_NodeFactor[u]->splay();
    }
    void link(long long u , long long v){
        assert(product_target_node);
        assert(!same(u,v));
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        m_EdgeFactor[u][v] = new SplayNode(u,v,init_v,false);
        m_EdgeFactor[v][u] = new SplayNode(v,u,init_v,false);
        evert(u);
        evert(v);
        m_NodeFactor[u]->splay();
        m_NodeFactor[v]->splay();
        merge(merge(merge(m_NodeFactor[u],m_EdgeFactor[u][v]),m_NodeFactor[v]),m_EdgeFactor[v][u]);
        m_NodeFactor[u]->splay();
    }
    void link(long long u , long long v , T w){
        assert(!same(u,v));
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        assert(!product_target_node);
        m_EdgeFactor[u][v] = new SplayNode(u,v,w,!product_target_node);
        m_EdgeFactor[v][u] = new SplayNode(v,u,w,false);
        evert(u);
        evert(v);
        m_NodeFactor[u]->splay();
        m_NodeFactor[v]->splay();
        merge(merge(merge(m_NodeFactor[u],m_EdgeFactor[u][v]),m_NodeFactor[v]),m_EdgeFactor[v][u]);
        m_NodeFactor[u]->splay();
    }
    void cut(long long u , long long v){
        assert(0 <= u && u < m_N);
        assert(0 <= v && v < m_N);
        assert(exist_edge(u,v));
        evert(u);
        long long l = find_EdgeFactor(u,v);
        long long r = find_EdgeFactor(v,u);
        m_NodeFactor[u]->splay();
        std::pair<SplayNode*,SplayNode*> tmp = split(r+1,m_NodeFactor[u]);
        tmp.first = split(r,tmp.first).first;
        tmp.first = split(l+1,tmp.first).first;
        tmp.first = split(l,tmp.first).first;
        merge(tmp.first, tmp.second);
        m_NodeFactor[u]->splay();
        m_NodeFactor[v]->splay();
        delete m_EdgeFactor[u][v];
        delete m_EdgeFactor[v][u];
        m_EdgeFactor[u][v] = nullptr;
        m_EdgeFactor[v][u] = nullptr;
    }
    void SubTreeUpdate(long long u , T x , long long p){
        assert(0 <= u && u < m_N);
        pair<SplayNode*,pair<SplayNode*,SplayNode*>> tmp = SplitSubTree(u,p);
        tmp.first->set_lazyUpdate(x);
        tmp.first->update();
        merge(merge(tmp.second.first, tmp.first),tmp.second.second);
    }
    void SubTreeAffine(long long u , T A , T B , long long p){
        assert(0 <= u && u < m_N);
        pair<SplayNode*,pair<SplayNode*,SplayNode*>> tmp = SplitSubTree(u,p);
        tmp.first->set_lazyAffine(A,B);
        tmp.first->update();
        merge(merge(tmp.second.first, tmp.first),tmp.second.second);
    }
    void SubTreeAdd(long long u , T x , long long p ){SubTreeAffine(u,T(1),x,p);}
    SplayNode SubTree(long long u , long long p){
        SplayNode res;
        assert(0 <= u && u < m_N);
        pair<SplayNode*,pair<SplayNode*,SplayNode*>> tmp = SplitSubTree(u,p);
        res = (*tmp.first);
        merge(merge(tmp.second.first, tmp.first),tmp.second.second);
        return res.copy();
    }
    SplayNode tour(int i , long long r){
        assert(0 <= r && r < m_N);
        assert(0 <= i && i < this->EulerTourSize(r));
        evert(r);
        SplayNode* rt = m_NodeFactor[r];
        rt->splay();
        rt = get_sub(i,rt);
        SplayNode res = *rt;
        res.parent = res.left = res.right = nullptr;
        return res;
    }
    void Debug(long long r){
        assert(0 <= r && r < m_N);
        evert(r);
        long long sz = EulerTourSize(r);
        cerr << "Debug From Root : " << root(r) << endl;
        SplayNode* rt = m_NodeFactor[r];
        rt->splay();
        for( int i = 0 ; i < sz ; i++){
            rt = get_sub(i,rt);
            cerr << "( " << rt->from << " , " << rt->to << " ) , value = " << rt->Value << endl;
        }
        m_NodeFactor[r]->splay();
    }
    vector<long long> euler_tour(long long r){
        assert(0 <= r && r < m_N);
        evert(r);
        vector<long long> res(0);
        SplayNode* rt = m_NodeFactor[r];
        rt->splay();
        long long sz = rt->SubTreeSize;
        rt = get_sub(0,rt);
        res.push_back(rt->to);
        for( int i = 0 ; i < sz ; i++){
            rt = get_sub(i,rt);
            if(rt->from != rt->to)res.push_back(rt->to);
        }
        return res;
    }
    vector<long long> euler_tour_compress(long long r){
        assert(0 <= r && r < m_N);
        evert(r);
        vector<long long> res,tmp;
        tmp = this->euler_tour(r);
        unordered_map<long long,priority_queue<long long>> first;
        unordered_map<long long,priority_queue<long long>> last;
        for(int i =0 ; i < tmp.size() ; i++){
            first[tmp[i]].push(-i);
            last[tmp[i]].push(i);
        }
        for(int i =0 ; i < tmp.size() ; i++){
            if(i == abs(first[tmp[i]].top()))res.push_back(tmp[i]);
            if(i == abs(last[tmp[i]].top()))res.push_back(tmp[i]);
        }
        return res;
    }
    SplayNode operator [](long long nodeID){
        m_NodeFactor[nodeID]->splay();
        SplayNode res = *(m_NodeFactor[nodeID]);
        return res.copy();
    }
    /*   
        Copyright ©️ (c) NokonoKotlin (okoteiyu) 2024.
        Released under the MIT license(https://opensource.org/licenses/mit-license.php) 
    */
};

使用例


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

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

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

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


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

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

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

    // Link-Cut Tree などと併用することで頂点 x の親頂点 p がわかるなら、
    // SubTree(x,p) で x 以降の部分木を表現するデータ (Splay Tree の根) を取り出せる
    // ただし x が根の場合は親の情報は不要 (なんでもいい)
    auto SubtreeDataCopy = ETT_V.SubTree(1,0);

    // SubTree のデータには、重みの Sum,Min,Max などが用意されている (今回は頂点重み)
    std::cerr 
        << SubtreeDataCopy.Sum << " , "
        << SubtreeDataCopy.Min << " , "
        << SubtreeDataCopy.Max 
    << std::endl;// -3 , -5 , 2

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

    // ある頂点が属する木の根の取得も可能
    std::cerr << ETT_V.root(4) << std::endl;// 1

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

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

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

    // 頂点 x の親頂点がわかっているなら、x 以下の部分木の重みの一律変更が可能
    // 頂点 1 以下の部分木に属する頂点重みを全て 102 に変更
    ETT_V.SubTreeUpdate(1,102,0);

    
    // 頂点 0 以下の部分木、つまり木全体。p はテキトーでいい
    ETT_V.evert(0);
    SubtreeDataCopy = ETT_V.SubTree(0,9);

    std::cerr 
        << SubtreeDataCopy.Sum << " , "
        << SubtreeDataCopy.Min << " , "
        << SubtreeDataCopy.Max 
    << std::endl;// 206 , -2 , 102

    // オイラーツアーに関する機能もあるけど、多分活躍しない
    vector<long long> ett = ETT_V.euler_tour(2);// 頂点 2 からのオイラーツアー列全体
    vector<long long> ettc = ETT_V.euler_tour_compress(2);// 初登場とラスト登場の丁度 2 回を記録した列全体
    // 頂点 3 から始まる++++独自定義++++のオイラーツアーの 1 番目の要素
    ETT_V.tour(1,2);
    /*
        少し実装を工夫して、Splay Tree の根から探索したら、一般的な定義のオイラーツアーの i 番目取得
        ができるが、めんどくさいのでやらない。使う場面もないだろうし。
        具体的には、get_sub の探索方法において、部分木サイズではなく、部分木内の辺要素の個数に注目して探索する。
    */

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

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

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

    // 辺重みを持つ場合、SubTreeUpdate などの対象が辺重みになる
    ETT_E.evert(0);
    ETT_E.SubTreeAffine(1,-2,14,0);// 部分木内の辺重み全てを -2 倍して 14 足す

    // 頂点 0 が属する木全体のデータ (辺重みの集約を持つ)
    auto SubtreeDataCopy2 = ETT_E.SubTree(0,0);

    std::cerr 
        << SubtreeDataCopy2.Sum << " , "
        << SubtreeDataCopy2.Min << " , "
        << SubtreeDataCopy2.Max 
    << std::endl;// 51 , -16 , 24
}

概要

各連結成分に対して NodeFactor と EdgeFactor を並べてオイラーツアーを表現

頂点 u を表す NodeFactor は SplayNode(u , u)
u から v に移動したことを表す EdgeFactor は SplayNode(u , v)

テンプレートパラメータの product_target_node の値によって、頂点に重みを持たせるか、辺に重みを持たせるかを決める

true の時、頂点重みを持つ
false の時、辺重みを持つ

重みを持つ方を product_target とする。頂点重みの場合は verify 済みですが、辺重みの方は verify していないので注意です。

計算量のボトルネックは平衡二分木の計算量に帰着します。

機能 & 仕様

product_target ではない要素の Value は未定義として、集約の計算時は無視する。

基本機能
- ComponentSize(r) := r が属する木のサイズ
- EulerTourSize(r) := r が属する木における r からのオイラーツアー列(ここでの定義通り)のサイズ
- update_val(i,x) := 頂点 i の重みを x にする
  - product_target が辺の時に呼ぶとエラー
- update_val(u,v,x) := 辺 (u-v) の重みを x にする
  - product_target が頂点の時に呼ぶとエラー
- evert(x) := x を連結成分の root にする
- link(x,y) := x,y の間に辺を追加 (元々 x,y は非連結)
  - product_target が辺の時に呼ぶとエラー
- link(x,y,w) := x,y の間に重み w の辺を追加 (元々 x,y は非連結)
  - product_target が頂点の時に呼ぶとエラー
- cut(x,y) := x,y から辺を削除 (元々 x,y に辺がある)
- root(x) := x の属する木の根
- same(x,y) := x,y が同じ木に属しているか
- operator[u] := 頂点 u の NodeFactor の SplayNode を返す
  - SplayNode のコピーは、隣接する SplayNode へのポインタを封印して返す
部分木について
- 頂点 u の部分木に関するクエリを処理できるが、頂点 u の親頂点 p がわかっていないといけない。u が根の場合は p は考えなくて OK (テキトーで OK)
  - 頂点 u の部分木に対応するオイラーツアーの区間を見つけるため (他にうまくやる方法はない)
  - u の親は ETT から計算することはできないので、LinkCutTree と併用する。
- SubTree(u,p) := 「u の部分木に対応するオイラーツアー列の区間」に対応する SplayNode のコピーを取得
  - SplayNode のコピーは、隣接する SplayNode へのポインタを封印して返す
- SubTreeUpdate(u,p,x) := u の部分木 (u 含む) の product_target の持つ値を一律に x に変更する
- SubTreeAffine(u,p,a,b) := u の部分木 (u 含む) の product_target の持つ値に一律に a かけて b 足す
- SubTreeAdd(u,p,x) := u の部分木 (u 含む) の product_target の持つ値に一律に x 足す
オイラーツアー
tour(i,r) := r が属する木における r からのオイラーツアーの i 番目の SplayNode (のコピー) を返す
euler_tour := オイラーツアー到達順に頂点番号を並べた std::vector。到達を全て記録。一般的なオイラーツアー
euler_tour_compress := オイラーツアーで、部分木に入る時/出る時のみ記録