全方位木 DP
木に対し、有向辺に対応する形で「値」が存在する場合に以下を得たい:
$ dp [u] [v] : 頂点 u から頂点 v に向かう辺に関しての「値」
※便宜的に v の代わりに u が持つ辺の v に対応する index とすると map とか使わずに済むので良い
$ dp\_sum [u] : 頂点 u から出る全辺に対しての「値」の和
「値」の例:辺 u - v で木を切った時の v 側に含まれる頂点の個数
dfs を2回行って上記を埋める。いずれも根から葉に向う形。
dfs1(u, p)
初期呼び出しは p = -1 等としておく
u の持つ辺のうち p との辺以外のものについての dfs1(v, u) の和を返す。(v は u と結ばれた頂点)
根について dp_sum が埋められる。その他の点については dp_sum が根を向く方向の辺を引いた値が埋められる。
全辺について根からの方向の dp を埋められる。
dfs2(u, p_val, p)
初期呼び出しは p = -1 等としておく
p_val として親側の「値」を渡す。初期呼び出しは省く。
p != -1 であれば dp_sum に p_val を足す。 dfs1 での dp_sum と合わせて全点について dp_sum が完成する。
p != -1 であれば $ dp [u] [p] として p_val を埋める。 dfs1 での dp と合わせて全辺について dp が完成する。
自身の完成した dp_sum から dfs1 で計算済みのその子に向かう辺の「値」を引けば、それは子から見た親側の「値」となる。これを p_val として dfs2 を子に対して適用していく。
以上により $ dp [u] [v] と$ dp\_sum [u] が $ O(N)で仕上がる。 dp_sum からある辺の値の差を取れないケースは辺の配列の左累積和と右累積和を用意してあげれば良い。
よって「値」は単位元と和の演算だけ定義できれば、すなわち例えばモノイドであれば全方位木 DP をする上で十分。