Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Dunsparce

C++でオイラーツアーのライブラリを作りました。

Last updated at Posted at 2024-03-07

　こちらの、オイラーツアーした木に対するクエリという記事を参考にして書かせていただきました。しかし、この記事にはpythonしかソースコードが載っていなかったので、C++でのライブラリを自作しました。詳細な説明は引用元が素晴らしいのでこの参考にさせていただいた記事を参照していただけると幸いです。(変数名などもこの記事に合わせているので、コンテスト中等でない限り、この記事を読んでから使用することを推奨します)
　また、間違い等ございましたらお教えください。

グラフの入力について

　このライブラリにおいてはグラフの型はvector<vector<Edge>>です。Edgeは重みなしでstruct Edge {long long to;};、重み付きでstruct Edge {long long to,cost;};、となっています。
　この型のグラフgを作り、euler_tour et(n,g)とすることもできますし、それが煩わしい場合にはeuler_tour et(n)とした後にet.add_edge(u,v)とすることも可能です。後述するサンプルコードを参考にしてください。

重みなしのオイラーツアー

　LCA(最小共通祖先) と 重みなしの距離を求めるオイラーツアーです。

使い方

　この構造体を張り付けた後、euler_tour 変数名(サイズ)で型を宣言します。

セグフォに注意
後述しますが、dfsをすることを忘れると、範囲外にアクセスしてしまいます。書き忘れないよう注意してください。

以下の表では変数名は et ということにしています。

行う事 関数 返り値 計算量 注意事項
辺の追加 et.add_edge(u,v) void O(1) 同様のことをEdgeの二次元配列を用意することで行うことができます。
dfs et.dfs(root) void O(N) たいていの場合root(根)は0としてしまって困ることはないと思います。また、辺を追加した後に必ず行ってください。initのようなものなので、忘れると範囲外アクセスを引き起こします。
二点間の最小共通祖先 et.lca(u,v) long long O(logN) uv間のlcaを求めます。
二点間の距離 et.dist(u,v) long long O(logN) uv間の距離を求めます。

ソースコード

LCA euler_tour.cpp
struct Edge {long long to;};
struct S_rmq {long long value; long long index;};
S_rmq op_rmq(S_rmq a, S_rmq b){
    if(a.value < b.value) return a;
    else return b;
}
S_rmq E_rmq(){return {(1LL << 60),-1LL};}

struct euler_tour {
    vector<long long> depth, visit;
    vector<long long> discover, finishing;
    vector<vector<Edge>> g;
    long long n;

    atcoder::segtree<S_rmq, op_rmq, E_rmq> rmq;

    euler_tour(long long n=1, vector<vector<Edge>> g=vector<vector<Edge>>()){
        init(n, g);
    }

    void init(long long n, vector<vector<Edge>> g){
        this->n = n;
        depth.clear();
        visit.clear();
        discover.assign(n, (1<<30));
        finishing.assign(n ,-1);
        this->g = g;
        this->g.resize(n);
    }

    void add_edge(long long u, long long v){
        g[u].push_back({v});
        g[v].push_back({u});
    }
    
    void dfs(long long root){
        Dfs(root, -1, 0);
        for(long long i=0;i<int(visit.size());i++){
            discover[visit[i]] = min(discover[visit[i]], i);
            finishing[visit[i]] = max(finishing[visit[i]], i+1);
        }
        vector<S_rmq> depth_v(int(depth.size()));
        for(long long i=0; i<int(depth.size()); i++){
            depth_v[i] = {depth[i], visit[i]};
        }

        rmq = atcoder::segtree<S_rmq, op_rmq, E_rmq>(depth_v);
    }

    void Dfs(long long v, long long p, long long d) {
        visit.push_back(v);
        depth.push_back(d);
        for (Edge u : g[v]) {
            if (u.to == p) continue;
            Dfs(u.to, v, d + 1);
            visit.push_back(v);
            depth.push_back(d);
        }
    }

    long long lca(long long u, long long v){
        return rmq.prod(min(discover[u], discover[v]), max(finishing[u], finishing[v])).index;
    }

    long long dist(long long u, long long v){
        return depth[discover[u]]+depth[discover[v]]-2*depth[discover[lca(u,v)]];
    }
};

使用例

LCA euler_tour_sample.cpp
#include <iostream>
#include <vector>
#include <atcoder/segtree>
//aclを利用していることに気を付けてください。
//ほかのコンテストサイトに提出する際は、aclのsegtreeをダウンロードするか、
//自前のセグ木で書き換えてください。
using namespace std;

//LCA euler_tourのコードを貼ってください(割愛します)

int main()
{
    int n; cin >> n;
    
    euler_tour et(n);
    for(int i=0;i<n-1;i++){
        int u,v; cin >> u >> v;
        u--; v--; //0indexedにしてください
        et.add_edge(u,v);
    }
    /*  
        こちらの書き方もできます
        vector<vector<Edge>> g(n);
        for(int i=0;i<n-1;i++){
            int u,v; cin >> u >> v;
            u--; v--;
            g[u].push_back({v});
            g[v].push_back({u});
        }
        euler_tour et(n,g);
    */
    et.dfs(0); //これを忘れないで下さい(セグフォります)
    
    cout << et.lca(2,3) << endl; //頂点2と頂点3のLCAを出力します。
    cout << et.dist(2,3) << endl; //頂点2と頂点3の距離を出力します。
}

atcoder提出 ABC-014-D 使用例 [249 ms]

重み付きオイラーツアー

　LCA(最小共通祖先) と 重み付きの距離、辺の重みの更新、任意の点を根としたときの木の持つ重みの和を求めるオイラーツアーです。

使い方

　この構造体を張り付けた後、weighted_euler_tour 変数名(サイズ)で型を宣言します。

以下の表では変数名は et ということにしています。

行う事 関数 返り値 計算量 注意事項
辺の追加 et.add_edge(u,v,w) void O(1) uv間にwの重みの辺を追加します。同様のことをEdgeの二次元配列を用意することで行うことができます。
dfs et.dfs(root) void O(N) たいていの場合root(根)は0としてしまって困ることはないと思います。また、辺を追加した後に必ず行ってください。initのようなものなので、忘れると範囲外アクセスを引き起こします。
二点間の最小共通祖先 et.lca(u,v) long long O(logN) uv間のlcaを求めます。
二点間の距離 et.dist(u,v) long long O(logN) uv間の距離を求めます。
任意の頂点を根とする部分木の頂点のコストの合計 et.sum(x) long long O(logN) dfsの時に関数の中に入れたrootを含まない方の部分木の辺のコストの合計です。
辺の重みの更新 et.update(u,v,x) void O(logN) uv間の辺の重みをxに変えます。そのような辺が存在しないときには何もしませんが、update関数内のコメントアウトをなくすことでそのようなときに出力を作ることができます。
辺の重みの更新 et.add(u,v,x) void O(logN) uv間の辺の重みにxを足します。そのような辺が存在しないときには何もしませんが、update関数内のコメントアウトをなくすことでそのようなときに出力を作ることができます。

ソースコード

weighted edge euler tour.cpp
struct Edge {long long to,cost;};
struct S_rmq {long long value; long long index;};
S_rmq op_rmq(S_rmq a, S_rmq b){
   if(a.value < b.value) return a;
   else return b;
}
S_rmq E_rmq(){return {(1LL << 60),-1LL};}
struct S_rsq {long long value;};
S_rsq op_rsq(S_rsq a, S_rsq b){return {a.value + b.value};}
S_rsq E_rsq(){return {0};}

struct weighted_euler_tour {
   vector<long long> depth, visit, cost1, cost2;
   vector<long long> discover, finishing;
   vector<vector<Edge>> g;
   long long n;
   map<pair<long long, long long>, long long> edge_index1;
   map<pair<long long, long long>, long long> edge_index2;

   atcoder::segtree<S_rmq, op_rmq, E_rmq> rmq;
   atcoder::segtree<S_rsq, op_rsq, E_rsq> rsq1;
   atcoder::segtree<S_rsq, op_rsq, E_rsq> rsq2;

   weighted_euler_tour(long long n=1, vector<vector<Edge>> g=vector<vector<Edge>>()){
       init(n, g);
   }

   void init(long long n, vector<vector<Edge>> g){
       this->n = n;
       depth.clear();
       visit.clear();
       discover.assign(n, (1<<30));
       finishing.assign(n ,-1);
       this->g = g;
       this->g.resize(n);
   }

   void add_edge(long long u, long long v, long long cost){
       g[u].push_back({v, cost});
       g[v].push_back({u, cost});
   }
   
   void dfs(long long root){
       cost1.push_back(0);
       cost2.push_back(0);
       Dfs(root, -1, 0);
       for(long long i=0;i<int(visit.size());i++){
           discover[visit[i]] = min(discover[visit[i]], i);
           finishing[visit[i]] = max(finishing[visit[i]], i+1);
       }
       vector<S_rmq> depth_v(int(depth.size()));
       for(long long i=0; i<int(depth.size()); i++){
           depth_v[i] = {depth[i], visit[i]};
       }
       vector<S_rsq> cost1_v(int(cost1.size()));
       for(long long i=0; i<int(cost1.size()); i++){
           cost1_v[i] = {cost1[i]};
       }
       vector<S_rsq> cost2_v(int(cost2.size()));
       for(long long i=0; i<int(cost2.size()); i++){
           cost2_v[i] = {cost2[i]};
       }

       rmq = atcoder::segtree<S_rmq, op_rmq, E_rmq>(depth_v);
       rsq1 = atcoder::segtree<S_rsq, op_rsq, E_rsq>(cost1_v);
       rsq2 = atcoder::segtree<S_rsq, op_rsq, E_rsq>(cost2_v);
   }

   void Dfs(long long v, long long p, long long d) {
       visit.push_back(v);
       depth.push_back(d);
       for (Edge u : g[v]) {
           if (u.to == p) continue;
           cost1.push_back(u.cost);
           cost2.push_back(u.cost);
           edge_index1[{min(v,u.to), max(v,u.to)}] = cost1.size()-1;
           edge_index2[{v, u.to}] = cost2.size()-1;

           Dfs(u.to, v, d + 1);
           visit.push_back(v);
           depth.push_back(d);
           cost1.push_back(0);
           cost2.push_back(-u.cost);
           edge_index2[{u.to, v}] = cost2.size()-1;
       }
   }

   long long lca(long long u, long long v){
       return rmq.prod(min(discover[u], discover[v]), max(discover[u], discover[v])).index;
   }

   long long pe(long long u){
       return rsq2.prod(0, discover[u]+1).value;
   }

   long long dist(long long u, long long v){
       if(u==v) return 0;
       return pe(u) + pe(v) - 2*pe(lca(u,v));
   }

   long long sum(long long x){
       return rsq1.prod(discover[x], finishing[x]).value;
   }

   void update(long long u, long long v, long long x){
       if(u > v) swap(u,v);
       if(edge_index1.find({u,v})==edge_index1.end()){
           //cout << "edge not found" << endl;
           return;
       }
       rsq1.set(edge_index1[{u,v}], {x});
       
       if(depth[discover[u]] > depth[discover[v]]) swap(u,v);
       rsq2.set(edge_index2[{u,v}], {x});
       rsq2.set(edge_index2[{v,u}], {-x});
   }

   void add(long long u, long long v, long long x){
       if(u > v) swap(u,v);
       if(edge_index1.find({u,v})==edge_index1.end()){
           //cout << "edge not found" << endl;
           return;
       }
       rsq1.set(edge_index1[{u,v}], {rsq1.prod(edge_index1[{u,v}], edge_index1[{u,v}]+1).value + x});
       
       if(depth[u] > depth[v]) swap(u,v);
       rsq2.set(edge_index2[{u,v}], {rsq2.prod(edge_index2[{u,v}], edge_index2[{u,v}]+1).value + x});
       rsq2.set(edge_index2[{v,u}], {rsq2.prod(edge_index2[{v,u}], edge_index2[{v,u}]+1).value - x});
   }
};

使用例

weighted_edge_euler_tour_sample
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <atcoder/segtree>
//aclを利用していることに気を付けてください。
//ほかのコンテストサイトに提出する際は、aclのsegtreeをダウンロードするか、
//自前のセグ木で書き換えてください。
using namespace std;

//weighted_euler_tourのコードを貼ってください(割愛します)

int main(){
    int n; cin >> n;

    weighted_euler_tour et(n);
    for(int i=0;i<n;i++){
        int u,v,w; cin >> u >> v >> w;
        u--; v--; //0indexedにしてください
        et.add_edge(u,v,w);
    }
    /*
        こちらの書き方もできます
        vector<vector<Edge>> g(n);
        for(int i=0;i<n-1;i++){
            int u,v,w; cin >> u >> v >> w;
            u--; v--;
            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
        weighted_euler_tour et(n,g);
    */
    et.dfs(0); //これを忘れないで下さい(セグフォります)

    cout << et.lca(2,3) << endl; //頂点2と頂点3のLCAを出力します。
    cout << et.dist(2,3) << endl; //頂点2と頂点3の距離を出力します。
    cout << et.sum(3) << endl; //頂点0を含まない方の部分木の辺の重みの合計を求めます。
    et.update(1,3,2); //頂点1,3間の辺の重みを2に変更します。
    et.add(1,3,1); //頂点1,3間の辺の辺の重みに1を加えます。つまり、重みは現在3です。
}

atcoder提出 ABC-294-G 使用例 [1059 ms]

終わりに

　結構長文となってしまいましたが(長文なのはコードの部分ですが)最後まで読んでいただきありがとうございます。できるだけ動作確認などしておりますが、間違いなどありましたら、教えていただけると幸いです。
　頂点に重みのあるオイラーツアーはそのような問題を見たことがないので作っていません。見かけたら作ります(絶対に痛い目を見る)。

3
0
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
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?