二乗の木DP
部分木のサイズに比例する大きさのdpテーブルをマージしていくタイプのDPの計算量はO(n2)
void dfs(int v, int p){ sz[v] = 1; dp[v] = {INF, s[v]}; for(auto &nv:g[v]){ if(nv == p) continue; dfs(nv, v); vl merged(sz[v]+sz[nv]+1, INF); rep(i, sz[v]+1){ rep(j, sz[nv]+1){ chmin(merged[i+j], dp[v][i]+dp[nv][j]); } } sz[v] += sz[nv]; dp[v] = merged; } dp[v]
参考: 木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ