Euler Tour

概要

木を経路で見ることで LCA や ノードの最短距離 が O(logN) で求まるデータ構造。 辺の重みも1回当たり O(logN) で変更可能な為、オンラインクエリにも対応出来る。

作成part

オイラーツアーした木に対するクエリ - Qiita

この記事に新規性はありません。maspyさんの記事、beetさんの記事がとても分かりやすいです。また、紹介しているテクニックはmaspyさんの記事で紹介されているものです。maspyさんの記事: …

qiita.com

method

• addEdge(u, v, w) : ノード u, v 間の重みが w の辺を追加する
• addVCost(i, w) : ノード i 自体に存在する頂点の重みを追加する
• changeECost(u, v, w) : ノード u, v 間の重みを w に変更する（辺を既に存在するものと仮定）
• lca(u, v) : ノード u, v の最近共通祖先（LCA）を返す

Program

// モノイド設定
using S = long long;
S Sum_e(){return 0;}
S Sum_op(S a,S b){return a+b;}

using U = pair<int,int>;
U Min_e(){return pair(1e9,1e9);}
U Min_op(U a,U b){return min(a,b);}

class EulerTour{
    public:
        EulerTour() : n(0),turn(0){}
        explicit EulerTour(const int &_n){
            n = _n;
            turn = 0;
            Graph.assign(n,{});
            vw.assign(n,0);
            finish.assign(n,0);
            discover.assign(n,0);
            v_cost1 = segtree<S, Sum_op, Sum_e>(2*n);
            e_cost1 = segtree<S, Sum_op, Sum_e>(2*n);
            v_cost2 = segtree<S, Sum_op, Sum_e>(2*n);
            e_cost2 = segtree<S, Sum_op, Sum_e>(2*n);
            depth_visit = segtree<U, Min_op, Min_e>(2*n);
        }

        inline void addEdge(const int &u, const int &v, const long long &w){
            Graph[u].emplace_back(pair(v,w));
            Graph[v].emplace_back(pair(u,w));
        }

        inline void addVCost(const int &i,const int &w){vw[i] = w;}

        inline void changeECost(int u, int v, const int &nw){
            // ※ Graph自体の更新はしていない
            if(discover[u] > discover[v])swap(u,v);
            // 辺は2回しか通らない → O(logN)で更新可
            e_cost1.set(discover[v],nw);
            e_cost2.set(discover[v],nw);
            e_cost2.set(finish[v],-nw);
        }

        inline S distV(const int &u, const int &v){return rootV(u) + rootV(v) - 2*rootV(lca(u,v)) + vw[lca(u,v)];}
        inline S distE(const int &u, const int &v){return rootE(u) + rootE(v) - 2*rootE(lca(u,v))               ;}
        inline S partV(const int &root){return v_cost1.prod(discover[root]  ,finish[root]);}
        inline S partE(const int &root){return e_cost1.prod(discover[root]+1,finish[root]);}

        inline int lca(int u, int v){
            if(u == v)return u;
            if(discover[u] > discover[v])swap(u,v);
            return depth_visit.prod(discover[u],finish[v]+1).second;
        }

        inline void build(){dfs(0,-1,0,0);}

    private:
        int n, turn;
        vector<vector<pair<int,long long>>> Graph;
        segtree<S, Sum_op, Sum_e> v_cost1, e_cost1, v_cost2, e_cost2;
        segtree<U, Min_op, Min_e> depth_visit;
        vector<long long> vw, discover, finish;

        // 0 → v の頂点・辺cost
        inline long long rootV(const int &v){return v_cost2.prod(0,discover[v]+1);}
        inline long long rootE(const int &v){return e_cost2.prod(1,discover[v]+1);}

        void dfs(const int &now, const int &pre,const int &w, const int &d){
            // 行きがけ処理
            discover[now] = turn;
            depth_visit.set(turn,U(d,now));
            v_cost1.set(turn,vw[now]);
            v_cost2.set(turn,vw[now]);
            e_cost1.set(turn,w);
            e_cost2.set(turn,w);
            turn++;
            for(auto &&[next,nw]:Graph[now]){
                if(next == pre)continue;
                dfs(next,now,nw,d+1);
            }
            // 帰りがけ処理
            finish[now] = turn;
            if(pre != -1)depth_visit.set(turn,U(d-1,pre));
            v_cost1.set(turn,0);
            e_cost1.set(turn,0);
            v_cost2.set(turn,-vw[now]);
            e_cost2.set(turn,-w);
            turn++;
        }
};