feature image

2022年10月28日 | ブログ記事

抽象化全方位木DPのライブラリとドキュメント

おしながき

はじめに

辺や頂点の重みを考慮して全方位木DPを抽象化するひとつの方法を紹介します。全方位木DPの説明はしません。
AtCoder Library のドキュメントに準い、要件と使用法を述べます。

RerootingDP

木に対して全方位木DPを行います。次の問題を解きます。

頂点 からなる 頂点の木 が与えられます。
有向グラフ は以下を満たします。

また、各有向辺には整数値の番号が割り当てられていて、 によって定められます。ここで としておきます。

可換モノイド と集合 および が与えられます。次の擬似コードに従って計算される値 dfs(0,0), dfs(1,1),...,dfs(n-1,n-1) を求めてください。ただし、頂点 を根と見たときの頂点 の子の頂点の集合を とします。

V dfs(vertex r, vertex v){
   E prod = e();
   for ( (v, c) in E, c in child(r,v) ){
       prod = merge(prod, put_edge(dfs(r,c),idx(v,c)));
   }
   return put_vertex(prod, v);
}

この問題を時間計算量 で解くことができます。

また、このライブラリはオラクルとして merge, e, put_edge, put_vertex を使用しますが、これらが定数時間で動くものと仮定したときの計算量を記述します。オラクル内部の計算量が である場合はすべての計算量が 倍となります。

コンストラクタ

RerootingDP<E, V, merge, e, put_edge, put_vertex> g(int n);

を定義する必要があります。

制約

計算量

add_edge

void g.add_edge(int u, int v, int idx1, int idx2)

制約

計算量

build

V g.build(int v)

制約

計算量

reroot

vector<V> g.reroot()

制約

計算量

使用例

AC code of https://atcoder.jp/contests/dp/tasks/dp_v

submission https://atcoder.jp/contests/dp/submissions/36003936

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint;

template<class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>
struct RerootingDP {
    struct edge{
        int from, to, idx, rev_idx;
    };
    RerootingDP (int _n = 0) : n(_n) { es.resize(n);}
    void add_edge(int u, int v, int idx1, int idx2){
        es[u].push_back({u,v,idx1,idx2});
        es[v].push_back({v,u,idx2,idx1});
    }
    V build(int v = 0){
        root = v;
        vis.resize(n,0);
        outs.resize(n);
        return dfs(root);
    }
    vector<V> reroot(){
        reverse_edge.resize(n);
        reverse_edge[root] = e();
        answers.resize(n);
        bfs(root);
        return answers;
    }
  private:
    int n, root;
    vector<vector<edge>> es;
    vector<int> vis;
    vector<vector<E>> outs;
    vector<E> reverse_edge;
    vector<V> answers;
    V dfs(int v){
        vis[v]++;
        E val = e();
        for (auto &p : es[v]){
            if (vis[p.to] > 0 && p.to != es[v].back().to) swap(p,es[v].back());
            if (vis[p.to] > 0) continue;
            E nval = put_edge(dfs(p.to),p.idx);
            outs[v].emplace_back(nval);
            val = merge(val,nval);
        }
        return put_vertex(val,v);
    }
    void bfs(int v){
        int siz = outs[v].size();
        vector<E> lui(siz+1), rui(siz+1);
        lui[0] = e(), rui[siz] = e();
        for (int i = 0; i < siz; i++) lui[i+1] = merge(lui[i],outs[v][i]);
        for (int i = siz-1; i >= 0; i--) rui[i] = merge(outs[v][i],rui[i+1]);
        for (int i = 0; i < siz; i++){
            reverse_edge[es[v][i].to] = put_edge(put_vertex(merge(merge(lui[i],rui[i+1]),reverse_edge[v]),v),es[v][i].rev_idx);
            bfs(es[v][i].to);
        }
        answers[v] = put_vertex(merge(lui[siz],reverse_edge[v]), v);
    }
};

mint merge(mint a, mint b){
    return a * b;
}
mint e(){
    return mint(1);
}
mint put_edge(mint v, int i){
    return v + 1;
}
mint put_vertex(mint e, int v){
    return e;
}

int main(){
    int n, m; cin >> n >> m;
    mint::set_mod(m);
    RerootingDP<mint,mint,merge,e,put_edge,put_vertex> g(n);
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v;
        g.add_edge(u-1,v-1,i,i);
    }
    g.build();
    for (auto ans : g.reroot()) cout << ans.val() << endl;
}

設計の意図

全方位木DPはすべての部分木 に対する答え を高速に求めるアルゴリズムで、 に含まれるさらに小さい部分木 に対する答え から を計算していきます。 を全体の根としたときの木DPの値を求める際、 の部分木を有向辺 に対応させると理解しやすい、という話があります。( を根としたときの の親です。 のときは は仮想的な頂点であり、有向辺 は仮想的な辺です。 )これに基づいて、有向辺 に対応する答えを と書くことにしましょう。 のときは仮想的な有向辺を考えており、対応する部分木は を根とする根付き木です。さて、このライブラリの設計では、

のような遷移式では考慮されない「辺の重み」を取り入れるため、補助的な関数 を定義しています。 に対応する部分木に辺 を付加するが頂点 はまだ付加しないみたいな(雰囲気で感じ取ってください)部分木もどきに対する答えっぽいもの(雰囲気で感じ取ってください)です。要点は次のとおりです。

ライブラリ内で辺に重み E e 、頂点に重み V v を持つような設計もあり得ると思ったのですが、できるだけライブラリの外側で問題依存パートを扱いたいのと、 put_vertex には単位元のようなものを要求しないため初期値の設定に困ったので、頂点・辺番号を引数に渡す関数を要求するライブラリの設計にしました。

おわり

抽象化の方法は唯一ではないです。より良い設計があれば教えてください。また、記事のわかりにくいところや誤りなどを発見されましたら、ご一報くださると大変ありがたいです。

謝辞

この記事のレビューをしてくれる方、ありがとうございます。先に感謝しておきます。

noya2 icon
この記事を書いた人
noya2

この記事をシェア

このエントリーをはてなブックマークに追加
共有
記事一覧 タグ一覧 Google アナリティクスについて