部分木のサイズに比例する大きさの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]+…