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 idx, int xdi)

制約

計算量

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/46008749

#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 to, idx, xdi;
    };
    RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) {
        es.resize(2*n-2);
        start.resize(2*n-2);
        if (n == 1) es_build();
    }
    void add_edge(int u, int v, int idx, int xdi){
        start[inner_edge_id] = u;
        es[inner_edge_id] = {v,idx,xdi};
        inner_edge_id++;
        start[inner_edge_id] = v;
        es[inner_edge_id] = {u,xdi,idx};
        inner_edge_id++;
        if (inner_edge_id == 2*n-2){
            es_build();
        }
    }
    vector<V> build(int root_ = 0){
        root = root_;
        vector<V> subdp(n); subdp[0] = put_vertex(e(),0);
        outs.resize(n);
        vector<int> geta(n+1,0);
        for (int i = 0; i < n; i++) geta[i+1] = start[i+1] - start[i] - 1;
        geta[root+1]++;
        for (int i = 0; i < n; i++) geta[i+1] += geta[i];
        auto dfs = [&](auto sfs, int v, int f) -> void {
            E val = e();
            for (int i = start[v]; i < start[v+1]; i++){
                if (es[i].to == f){
                    swap(es[start[v+1]-1],es[i]);
                }
                if (es[i].to == f) continue;
                sfs(sfs,es[i].to,v);
                E nval = put_edge(subdp[es[i].to],es[i].idx);
                outs[geta[v]++] = nval;
                val = merge(val,nval);
            }
            subdp[v] = put_vertex(val, v);
        };
        dfs(dfs,root,-1);
        return subdp;
    }
    vector<V> reroot(){
        vector<E> reverse_edge(n);
        reverse_edge[root] = e();
        vector<V> answers(n);
        auto dfs = [&](auto sfs, int v) -> void {
            int le = outs_start(v);
            int ri = outs_start(v+1);
            int siz = ri - le;
            vector<E> rui(siz+1);
            rui[siz] = e();
            for (int i = siz-1; i >= 0; i--){
                rui[i] = merge(outs[le+i],rui[i+1]);
            }
            answers[v] = put_vertex(merge(rui[0],reverse_edge[v]),v);
            E lui = e();
            for (int i = 0; i < siz; i++){
                V rdp = put_vertex(merge(merge(lui,rui[i+1]),reverse_edge[v]),v);
                reverse_edge[es[start[v]+i].to] = put_edge(rdp,es[start[v]+i].xdi);
                lui = merge(lui,outs[le+i]);
                sfs(sfs,es[start[v]+i].to);
            }
        };
        dfs(dfs,root);
        return answers;
    }
    private:
    int n, root, inner_edge_id;
    vector<E> outs;
    vector<edge> es;
    vector<int> start;
    int outs_start(int v){
        int res = start[v] - v;
        if (root < v) res++;
        return res;
    }
    void es_build(){
        vector<edge> nes(2*n-2);
        vector<int> nstart(n+2,0);
        for (int i = 0; i < 2*n-2; i++) nstart[start[i]+2]++;
        for (int i = 0; i < n; i++) nstart[i+1] += nstart[i];
        for (int i = 0; i < 2*n-2; i++) nes[nstart[start[i]+1]++] = es[i];
        swap(es,nes);
        swap(start,nstart);
    }
};

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 には単位元のようなものを要求しないため初期値の設定に困ったので、頂点・辺番号を引数に渡す関数を要求するライブラリの設計にしました。

実装上の工夫(追記 : 2023/09/28)

内部で保持する木の構造を二次元配列から一次元配列で持つように変更しました。
また、左右で累積を取る reroot 内部の処理を、右側の累積のみ記録するように変更しました。

おわり

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

謝辞

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

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

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年12月10日
HACK TO THE FUTURE 2024 に参加しました!
noya2 icon noya2
2023年11月29日
ICPC 2023/24 Asia Yokohama Regional Contest 参加記(noya2 視点)
noya2 icon noya2
2023年9月10日
作問ハッカソン2023を開催しました!
noya2 icon noya2
2023年7月23日
作問ハッカソン2023 を開催します!
noya2 icon noya2
2023年7月8日
ICPC国内予選2023参加記(noya2視点)
noya2 icon noya2
2023年4月29日
CPCTF2023 PPC作問陣 Writeup
noya2 icon noya2
記事一覧 タグ一覧 Google アナリティクスについて