SRM 643 Div2 1000 TheKingsFactorization

問題概要
木のノードに色を付ける。
色は赤か緑のどちらかを使わなければならない。
あるノードを色xで塗るときのコストは、そのノード以下の部分木で色xで塗られたノードの数に等しい。
すべてのノードを塗るのに必要な最小コストを求めよ。

解法
よくある 木のDP。
根付き木の場合は、親子関係からトポロジカル順序が決まるのでDPで解きやすい。
今回の場合は、状態数を（ノード, そのノード以下の部分木中の何個のノードを赤で塗るか）という形で持っておくことで、すべての子ノードの部分問題が解ければ、親ノードの問題も解ける。
ここで、親ノードで持っている赤ノードの数を、それぞれの子ノードに分配するパターンを全通り試さなければならないが、ここには古典的なナップサック問題が応用できる。
DP in Tree, DP in DPということで面白かった問題。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const int oo = 1<<28;
vector<int> g[55];
int dp[55][55];
int nums[55];

class TheKingsTree {
  void solve(int v) {
    nums[v] = 1;
    for (auto &w: g[v])
      nums[v] += nums[w];

    int ks[55][55];
    REP (i, 55) REP (j, 55) ks[i][j] = oo;
    ks[0][0] = 0;

    for (int i = 0; i < g[v].size(); i++) {
      for (int j = 0; j <= nums[v]; j++) {
        for (int k = 0; j + k <= nums[v]; k++) {
          ks[i+1][j+k] = min(ks[i+1][j+k], ks[i][j] + dp[g[v][i]][k]);
        }
      }
    }

    for (int r = 0; r < nums[v]; r++) {
      dp[v][r+1] = min(dp[v][r+1], ks[g[v].size()][r] + r + 1);
      dp[v][r] = min(dp[v][r], ks[g[v].size()][r] + nums[v] - r);
    }
  }

public:
  int getNumber(vector<int> parent) {
    int n = parent.size() + 1;
    REP (i, 55) g[i].clear();
    REP (i, 55) REP (j, 55) dp[i][j] = oo;
    REP (i, parent.size()) g[parent[i]].push_back(i+1);
    
    for (int i = n-1; i >= 0; i--)
      solve(i);
    
    int ret = oo;
    REP (i, 55) ret = min(ret, dp[0][i]);
    return ret;
  }
};