poj3342Party at Hali-Bula（树形dp）

/*
   树形dp！
   判重思路：
   当dp[v][0]==dp[v][1]时，很自然，flag[u][0]必然是有两种方案的。flag[u][1]则不然，
   因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时，则必然flag[u][1]也不唯一
   也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样)，那么父节点u不选的时候一定会有
   多种方案！也就是flag[u][0]=false; 否则如果flag[v][0]==flase（子节点不选的时候有多种方案）,
   那么父节点u选择的时候一定有多种方案，则flag[u][1]=false;
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#define N 205
using namespace std;

map<string, int>mp;
int n;
int cnt;
int g[N][N];
int dp[N][2];
bool flag[N][2];
map<string, int>::iterator it;

void dfs(int u){
   for(int v=1; v<=n; ++v)
       if(g[u][v]){
          dfs(v);
          dp[u][1]+=dp[v][0];
          dp[u][0]+=max(dp[v][1], dp[v][0]);
          if(dp[v][1]==dp[v][0]) flag[u][0]=false;
          if(flag[v][0]==false) flag[u][1]=false;
       } 
}

int main(){
   string na1, na2;
   while(scanf("%d", &n) && n){
       mp.clear();
       memset(g, 0, sizeof(g));
       cnt=0;
       cin>>na1;
       mp[na1]=++cnt;
       for(int i=1; i<n; ++i){
           dp[i][1]=1;
           dp[i][0]=0;
           flag[i][1]=flag[i][0]=true;
           cin>>na1>>na2;
           it=mp.find(na1);
           if(it==mp.end())
              mp[na1]=++cnt;
           it=mp.find(na2);
           if(it==mp.end())
               mp[na2]=++cnt;
           g[mp[na2]][mp[na1]]=1; 
       }
       dp[n][1]=1;
       dp[n][0]=0;
       flag[n][1]=flag[n][0]=true;
       dfs(1); 
       if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s\n", dp[1][1], "Yes");
       else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s\n", dp[1][0], "Yes");
       else printf("%d %s\n", max(dp[1][0], dp[1][1]), "No");
   }
   return 0;
}