traPさんの抽象化全方位木DPライブラリとそのチートシート

ライブラリ本体

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

　この traP 様のライブラリのおかげで命拾いをしたので、感謝をこめて、また、自分が再び使うときにより速く利用できるようにチートシートをまとめます。

チートシート（基本）

部分木

using S = long long;
vector<S> node;
S merge(S a,S b){
    return a+b;
}
S e(){
    return 0;
}
S put_edge(S x,int i){
    return x;
}
S put_vertex(S x,int i){
    return x+node[i];
}

※このままだと全頂点の重みがでてくるだけなので、改造前提です

最遠頂点

using S = long long;
S merge(S a,S b){
    return max(a,b);
}
S e(){
    return 0;
}
S put_edge(S x,int weight){
    return x+weight;
}
S put_vertex(S x,int i){
    return x;
}

※ put_edge の第 $2$ 引数は、頂点番号を引いてくる想定ですが、weight のように、ここに直接情報を載せることもできます。

考え方

　このライブラリでは、

• merge
• e
• put_edge
• put_vertex

　という $4$ つの関数を設定します。e はいわゆる単位元で、それ以外の関数は下図のような感じです。

　個人的な感触では、put_edge は辺を「またいだ」ときの処理、put_vertex は頂点に「到着した」ときの処理と考えると理解しやすいかなと思います。

　最遠頂点をテーマに、具体的なコードや数字で考えてみます。

　以下のようなグラフに対して、最遠頂点を求めてみます。

int main(){
    int n;
    cin >> n;
    RerootingDP<S,S,merge,e,put_edge,put_vertex> dp(n);
    for(int i=0;i<n-1;i++){
        int a,b,w;
        cin >> a >> b >> w;
        a--;
        b--;
        dp.add_edge(a,b,w,w);
    }
    cout << "build" << endl;
    for(auto ans:dp.build()){
        cout << ans << endl;
    }
    cout << "reroot" << endl;
    for(auto ans:dp.reroot()){
        cout << ans << endl;
    }
}

output

build
6
4
0
0
0
reroot
6
7
10
11
11

　チートシート（基本）に載っているのはかなり単純な命令なので、全方位木 dp が想定される問題ではより複雑なモノイドを載せることが多いと想定されます。そこら辺はセグ木を改造できる技術があれば大丈夫かなと思います。

チートシート（やや発展）

最遠頂点（頂点番号つき）

struct S
{
    long long path;
    long long vert_idx;
};
S merge(S a,S b){
    if(a.path<b.path){
        return b;
    }else{
        return a;
    }
}
S e(){
    return {0,-1};
}
S put_edge(S x,int weight){
    x.path += weight;
    return x;
}
S put_vertex(S x,int i){
    if(x.vert_idx == -1){
        return {0,i}; // 端だったときのみ頂点番号を設定
    }else{
        return x;
    }
}

重みつき頂点の総和

vector<long long> node;
struct S
{
    long now;
    long sum;
};
S merge(S a,S b){
    return {a.now+b.now,a.sum+b.sum};
}
S e(){
    return {0,0};
}
S put_edge(S x,int i){
    x.now += x.sum;
    return x;
}
S put_vertex(S x,int i){
    x.sum += node[i];
    return x;
}