問題と、その問題で使ったモノイドなどを記載していく
TODO: いい絵がほしい
$\mathrm{dp}[v][i] =$ 頂点 $v$ に接続している $i$ 番目の有向辺の先にある部分木に関する値
↓ Rust で書くと DP の遷移はこんな感じ。
dp[current_v][current_e] = {
let next_v = adj[current_v][current_e];
let vals = (0..adj[next_v].len())
.filter(|&next_e| adj[next_v][next_e] != current_v)
.map(|edge_j| self.add_edge(&dp[next_v][next_e], next_v, next_e))
.collect_vec();
let prod = Self::prod(&vals);
self.add_vertex(&prod, next_v)
};
愚直に実装すると、$O(V^2)$ みたいな計算量になるが、工夫して計算すると $O(V)$ になる。