SRM 662 div1 med: ExactTree
気づかなかった…
解法
S(T)は,別の見方をすると,「ある頂点から別の頂点に向かうときに,それぞれの辺を何回通るか,の総和」とみなすことが出来ます(頂点単位でゴニョゴニョ考えるのではなく辺単位で考える)
ある辺を追加することを考えます。それが頂点数pの木と頂点数qの木(頂点数qの木はこれから頂点を伸ばしていって合計頂点数をnにする)につながる場合,その辺を通る経路の数は,頂点数pの木からq側の木に向かう経路の数分だけあるのでp*(n-p)です。
よって,dp[頂点数][余り] = 最小コスト というdpを作れば問題が解けます。
const int MAXN = 55; const int MAXM = 101; const int INF = 1e9; int dp[MAXN][MAXM]; class ExactTree { public: int getTree(int n, int m, int r) { for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXM; j++) dp[i][j] = INF; dp[1][0] = 0; for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) { for (int x = 0; x < m; x++) for (int y = 0; y < m; y++) { if (dp[j][x] >= INF || dp[i-j][y] >= INF) continue; int z = dp[j][x] + dp[i-j][y] + j*(n-j); dp[i][z%m] = min(dp[i][z%m], z); } } } int ans = dp[n][r]; if (ans >= INF) ans = -1; return ans; } };