POJ 2342 Anniversary party

問題

N人のうちから何人かパーティに招待したい。N人には上司部下の関係が存在し、これらは一つの木構造をなしている。（つまり、ある一人にたいして上司はせいぜい一人しかおらず、上司のいない人間はただ一人である）
パーティには部下とその直属の上司が同時に出席できない、という制限を設けた時、パーティの楽しさを最大化せよ。ただしパーティの楽しさは招いた人のconvivialityの和として定義される。

やりかた

木DP。
dp[idx][prevuse]:=（頂点idxを根とする部分木において、idxの親をパーティに招いたかどうかを状態として持たせた場合のconvivialityの最大値）

このように置くと、
idxの親を招いた場合にはidxを招くことはできず、
招いていない場合には、idxを招くことができるし、招かないこともできる。

convivialityがマイナスの場合はそもそも招かなくていい。
以下ソース。

int p[6001], dp[6001][2];
vector<vector<int> >g;

int dfs(int idx, bool prevuse){
  if(dp[idx][prevuse] != -1) return dp[idx][prevuse];
  
  int ret = 0;
  if(prevuse){//idxの親を招いている場合
    for(int i = 0; i < g[idx].size(); i++){
      int next = g[idx][i];
      ret += dfs(next, false);
    }
  }else{//招いていない場合
    int s1 = 0, s2 = 0;
    for(int i = 0; i < g[idx].size(); i++){
      int next = g[idx][i];
      s1 += dfs(next, false); //idxを招く
      s2 += dfs(next, true);  //idxを招かない
    }
    ret = max(s1, s2 + max(p[idx], 0));
  }
  return dp[idx][prevuse] = ret;
}


int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  g.clear();
  g.resize(N);
  for(int i = 0; i < N; i++) scanf("%d", p + i);

  int a, b;
  vector<bool> f(N, false);
  for(int i = 0; i < N - 1; i++){
    scanf("%d %d", &a, &b);
    g[b - 1].push_back(a - 1);
    f[a - 1] = true;
  }
  int s;
  for(s = 0; s < N; s++) if(!f[s]) break;//探索は根から始める
  FILL(dp, -1);

  printf("%d\n", dfs(s, false));
  scanf("%d %d", &a, &b);
  return 0;
}