UVa 1220 : 3794 - Party at Hali-Bula

UVa演習 2014/6/17 (木) 問1

問題リンク : http://uva.onlinejudge.org/external/12/1220.html

問題概要：
とある会社の社員達がパーリィを開くことにした
Big Bossと呼ばれる社員以外はちょうど１人のボスをもつ(つまり、ツリー状のグラフになる)
パーリィに社員とその直接のボスの2人を呼ぶことはできない
最大何人パーリィに呼べるか？
またその最大となるような呼び方は一意に定まるか？

解法：
木のDPをする
ルートから再帰でみていく
その際に、
１,今みている社員をパーリィに呼ぶ場合
=> 子ノードの結果のうち、子を呼ばない場合の結果と足し合わせる
２,今みている社員をパーリィに呼ばない場合
=> 子ノードを呼ぶ場合と呼ばない場合の最大値が一緒ならどちらを選択しても良い == 一意に定まらない
　　そうでない場合、呼んだ場合と呼ばない場合の最大値が大きいほうを選ぶ

最終的な結果、ルートを呼んでも呼ばなくても結果が同じなら一意に定まらない

結果:
1WA
２の場合の考察が甘かった

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

using namespace std;

typedef pair<int,int> ii;
typedef pair<ii,ii> ii2;

int n;
vector<int> G[201];
ii dp[201][2];

ii2 dfs(int cur){

  if( dp[cur][0] != ii(-1,-1) ) return ii2(dp[cur][0],dp[cur][1]);

  ii2 ret = ii2(ii(0,0),ii(0,0));

  rep(i,G[cur].size()){

    ii2 tmp = dfs(G[cur][i]);

    if( tmp.F.first == tmp.S.first ) {
      ret.F.first += tmp.F.first;
      ret.F.second = true;
    } else {
      if( tmp.S.first > tmp.F.first ) {
        ret.F.first  += tmp.S.first;
        ret.F.second |= tmp.S.second;
      } else {
        ret.F.first  += tmp.F.first;
        ret.F.second |= tmp.F.second;
      }
    }

    ret.S.first  += tmp.F.first;
    ret.S.second |= tmp.F.second;

  }

  ret.S.first++;

  dp[cur][0] = ret.F;
  dp[cur][1] = ret.S;
  
  return ii2(dp[cur][0],dp[cur][1]);
}

int main(){
  while( cin >> n, n ){
    rep(i,n) G[i].clear();
    map<string,int> mp;
    int idx = 0;
    string tmp;
    cin >> tmp;
    mp[tmp] = idx++;
    rep(i,n-1){
      cin >> tmp;
      if( !mp.count(tmp) ) mp[tmp] = idx++;
      int v1 = mp[tmp];
      cin >> tmp;
      if( !mp.count(tmp) ) mp[tmp] = idx++;
      int v2 = mp[tmp];
      G[v2].push_back(v1);
    }

    rep(i,n) rep(j,2) dp[i][j] = ii(-1,-1);
    rep(i,n) if( G[i].empty() ) {
      dp[i][0] = ii(0,0);
      dp[i][1] = ii(1,0);
    }

    ii2 tmp_ii2 = dfs(0);
    ii res;
    if( tmp_ii2.F.first < tmp_ii2.S.first )  res = tmp_ii2.S;
    else                                     res = tmp_ii2.F;
    if( tmp_ii2.F.first == tmp_ii2.S.first ) res.second = true;

    if( res.second ) {
      printf("%d No\n",res.first);
    } else {
      printf("%d Yes\n",res.first);
    }

  }
  return 0;
}