rerooting.md

title	documentation_of
Rerooting （全方位木 DP）	./rerooting.hpp

できること

• ここに記述する内容はリンク [1] で説明されていることとほぼ同等．
• 木の各頂点・各辺になんらかのデータ構造が載っている．
• 根付き木について，各頂点 $v$ を根とする部分木に対して計算される Subtree 型の情報を $X_v$ とする．また，各辺 $uv$ が持つ Edge 型の情報を $e_{uv}$ とする．
• $X_v$ は $X_v={\mathrm{add}}_{\mathrm{vertex}}(\mathrm{rake}({\mathrm{add}}_{\mathrm{edge}}(X_{c_1},c_1,e_{v{c}_1}),\dots ,{\mathrm{add}}_{\mathrm{edge}}(X_{c_k},c_k,e_{v{c}_k})),v)$ を満たす．ここで $c_1,\dots ,c_k$ は $v$ の子の頂点たち．
  • ${\mathrm{add}}_{\mathrm{edge}}(X_v,v,e_{uv})$ は $u$ の子 $v$ について Children 型の情報を計算する関数．
  • ${\mathrm{add}}_{\mathrm{vertex}}(y,v)$ は Children 型の引数 $y$ をもとに頂点 $v$ における Subtree 型の情報を計算する関数．
  • $\mathrm{rake}(y_1,\dots ,y_k)$ は任意個の Children 型の引数の積を計算する関数．
  • $\mathrm{rake}()$ には結合法則が成立しなければならない．また， Children 型の単位元を e() とする．
• 以上のような性質を満たすデータ構造を考えたとき，本ライブラリは森の各頂点 $r$ を根とみなしたときの連結成分に関する $X_r$ の値を全ての $r$ について線形時間で計算する．

使用方法（例）

vector<int> inD;
struct Subtree {
    bool exist;
    int oneway, round;
};
struct Children {
    bool exist;
    int oneway, round;
};
Children rake(Children x, Children y) {
    if (!x.exist) return y;
    if (!y.exist) return x;
    return Children{true, min(x.oneway + y.round, y.oneway + x.round), x.round + y.round};
}
Children add_edge(Subtree x, int, tuple<>) {
    if (!x.exist) return {false, 0, 0};
    return {true, x.oneway + 1, x.round + 2};
}
Subtree add_vertex(Children x, int v) {
    if (x.exist) return {true, x.oneway, x.round};
    return {inD[v], 0, 0};
    return {false, 0, 0};
}
Children e() { return {false, 0, 0}; }


vector<vector<pair<int, tuple<>>>> to;
rerooting<tuple<>, Subtree, Children, rake, add_edge, add_vertex, e> tree(to);
tree.run();
for (auto x : tree.dpall) cout << x.oneway << '\n';

また，メソッド get_subtree(int root, int par) によって，木を頂点 par （par が $-1$ の場合は root）を根とした根付き木として見た場合の頂点 root を根とする部分木の情報が取得できる．

int u, v;  // u-v 間に辺が存在
Subtree s1 = tree.get_subtree(u, v);

問題例

• エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222） F - Expensive Expense
• AOJ 1595: Traffic Tree
• No.1718 Random Squirrel - yukicoder
• トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298) Ex - Sum of Min of Length
  • get_subtree() を使用するのが楽．

リンク

1. 全方位木DP(ReRooting)の抽象化について - メモ帳
2. 解説 - エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）
3. 競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん