全方位木DP

木に関するDP手法の一種。

木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】 | アルゴリズムロジック

概要

詳細なアルゴリズムは、他の記事が多く出てくるのでそちら参照。

「木で、ある頂点を中心に考えたときの何らかの値」を「全ての頂点について」求めたいときに使うことがある。

①を根として木DPを行うことで、①を中心に考えたときの値を求められるような問題があったとする。

このとき、頂点②を中心に考えたいとき、最初からまた木DPを行うのでなく、 ①を計算したときの結果を上手くずらして使うことで、計算量を削減できる。

    ①             ②
  ／  ＼         ⇙⇓＼     ②から④,⑤方向への部分木 および
 ②    ③  →   ④ ⑤ ①    ①から③方向への部分木は
 /\    /\             ⇓    ①を根としたDPで求まっている（二重矢印）
④⑤  ⑥⑦            ③    
                     ⇙⇘    あとは、親子関係を①→②から②→①に
                    ⑥  ⑦   付け替えたときの差分を計算すればよい。
                             （DP[1] から DP[2] に相当する分を除き、
                               DP[2] にはその除いた分を加える）

1つ頂点を遷移するたびに、1本の辺の付け替えさえ計算すればいい。
これを $O(1)$ でできるなら、根からのDFSを2回行うことで、$O(N)$ で計算できて嬉しい。

条件

DPに乗せる値と、その値同士をマージする演算が可換モノイドであればよい。

つまり、DPに乗せる値 $a,b,c,...$ とその間の演算 $\cdot$ があって、

結合法則が成り立つ
- $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
単位元 $e$ が存在する
- 任意の $a$ について、$a \cdot e = e \cdot a = a$
可換である
- $a \cdot b = b \cdot a$

が成り立てばよい。

厳密には「可換である」は必要条件では無い。
ただ、順番に意味があるなら、それぞれの頂点に対して子の順序が決まっているということなので、ちょっと特殊である。
~~実装が面倒くさくなるので、~~ここでは可換を前提とする。

抽象化

骨組みをライブラリ化して、必要な関数のみ外部注入することで、コーディング量を減らしたい。

アルゴリズムのおさらい

木DPのアルゴリズムを、頂点 $v$ を中心に考える。

問題によっては省略できる処理もあるが、だいたい求められるのは以下のような流れかと思う。

1回目のDP

$DP1[v]=$ 根を固定した場合に、頂点 $v$ 以下の部分木の値

$v$ が葉なら所定の値を置いて終わり（★1）
$v$ が節なら
- 子の値が求まっていなければ子のDPの値を先に求める
- 各 $DP1[子]$ の値から $DP1[v]$ を求めるために加工する（★2）
  - 加工された値を、「加工値」と呼ぶことにする
- 全ての子の加工値をマージする（★3）
- マージ結果に自身の値を反映させる（★4）
- それを $DP1[v]$ とする

ここで、「加工」「マージ」「反映」の具体例については、例えば以下の例題で

例題
- 木があり、頂点 $i$ に $A_i$、辺 $i$ に $B_i$ のコストがそれぞれ設定されている
- $f(u,v)$ を「$u,v$ 間を最短で結ぶパスで通過する頂点と辺のコストの総和」とする
- $u=1,2,...$ について、$v$ は任意に決められる場合に、$f(u,v)$ の最大値をそれぞれ求めよ

      ⓟ         DP1[u] = 15, DP1[w] = 12, Av=9 とする。
      ↓2
      ⓥ         DP1[v]を求めるには、各子の値に辺のコストを加算して
   ↙3  5↘      15+3, 12+5 とする処理がいる。これを「加工」とする。
  ⓤ      ⓦ
  ↓...   ↓...  今回は最大値を求めたいので、max(18, 17) が「マージ」となる。
                 
                 さらに、v自身の値も加算する処理がいる。18+9
                 これを「反映」とする。
                 
                 以上より、DP1[v]=27 となる。

2回目のDP

$DP2[v]=$ 頂点 $v$ を根とした場合の値（求めたい値）

親から“もし親が $v$ の子だった場合の加工値” $p$ が与えられる
$DP2[v]$ を求める
- 全ての子の加工値のマージ結果に $p$ をマージする（★3）
- マージ結果に自身の値を反映させる（★4）
- それを $DP2[v]$ とする
それぞれの子 $u$ に伝播させる
- $u$ 以外の子の加工値と、$p$ をマージする（★3）
- マージ結果に自身の値を反映させる（★4）
- その値を、$DP2[u]$ に反映させるために加工する（★2）
- $u$ にその値を伝える

手順の整理

★1～★4のざっくり4つの関数が、抽象化のために必要になる。

しかし、よく考えるとDP1には★4の結果を置く必要性があまりない。
どっちみち2回目のDPで、★3の結果と $p$ をマージしなおして、改めて★4を行うため。

なので、1回目のDPの★4については★2と一緒にしてしまえる。
（DP1には★3までの結果を置き、次に親に伝播させるタイミングで★4と★2の処理を同時に行う）

「DP1は、子をマージするところまでの結果で、自身の頂点の値は反映前」とした方が無駄が無い。

そうすると2回目のDPで $u$ に伝播させる際の★4→★2もまとめることができる。

1回目のDP（整理後）

$DP1[v]=$ 根を固定した場合に、頂点 $v$ を未反映の、$v$ 以下の部分木のマージ結果

$v$ が葉なら所定の値を置いて終わり（★1）
$v$ が節なら
- 子の値が求まっていなければ子のDPの値を先に求める
- 各 $DP1[子]$ の値に子頂点の値を反映させ、$DP1[v]$ のために加工する（★4→2）
- 全ての子の加工値をマージする（★3）
- それを $DP1[v]$ とする

2回目のDP（整理後）

親から“もし親が $v$ の子だった場合の加工値” $p$ が与えられる
$DP2[v]$ を求める
- 全ての子の加工値のマージ結果に $p$ をマージする（★3）
- マージ結果に自身の値を反映させる（★4）
- それを $DP2[v]$ とする
それぞれの子 $u$ に伝播させる
- $u$ 以外の子の加工値と、$p$ をマージする（★3）
- マージ結果に自身の値を反映させ、$DP2[u]$ のために加工する（★4→2）
- $u$ にその値を伝える

こうなる。

ここで、2回目のDPの★4（単独）の部分は★4→2の関数の引数に加工フラグを持たせ、 Falseの場合は★2に相当する処理を行わないとすれば、結局、定義すべき関数は3つになる。

DPに乗せる値の型を T として、

★1: leaf(v) → T
- 葉頂点 $v$ に乗せるDPの値を返す
★4→2: apply(dp_u:T, u, v, edge, flag:bool) → T
- $DP[u]$ に頂点 $u$ の値を反映し、$edge$ をたどって $DP[v]$ のために加工する
★3: merge(a:T, b:T) → T
- 2つの加工値をマージする

さらに、DPの値をマージする元となる、単位元を返す関数 unit() → T もあると実装しやすくなる。

この4つを定義することで、全方位木DPを抽象化できる。

ただ、applyに関しては、問題によってはもう少し何らかの引数を増やす必要が生じるかも知れない？

目次