2 乗の木 DP は O(N^2) になる

タイトルが小泉進次郎すぎる

概要

$dp[i][j]$ のうち、$0\leq j\leq |\mathrm{children}(i)|$ に定義されて、子から遷移していくタイプの木 DP では、計算量が $O(N^2)$ になる（常識）

$N$ 個の頂点をマージしていく形に帰着できる。サイズ $S_l$ と $S_r$ のグループをマージするときには $S_lS_r$ の計算量がかかる。 これを、グループ内の頂点どうしに辺を張る、と解釈すれば、最終的には完全グラフができるので、辺数 $=$ ならし計算量は $O(N^2)$。