【UVA】1220-Party at Hali-Bula?(동적 계획, 트리)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<string>
#include<sstream>
#include<ctime>
using namespace std;
#define _PI acos(-1.0)
#define INF 1 << 10
#define esp 1e-6
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pill;
/*===========================================
===========================================*/
#define MAXD 200 + 10
map<string,int>person;  /*       */
vector<int>G[MAXD];
int n;
int size ,ans;
int dp[MAXD][2];
/*dp[c][1]    c           ，dp[c][0]    c        */
int fp[MAXD][2];
/*fp[c][1]    c          ,  fp[c][0]    c       */
bool Input(){
    size = 1;
    person.clear();
    cin >> n;
    if(!n)
        return false;
    string name;
    string s1[MAXD],s2[MAXD];
    cin >> name;
    person[name] = size++;
    for(int i = 0 ; i < n - 1; i++){
         cin >> s1[i] >> s2[i];
         if(!person[s1[i]])
            person[s1[i]] = size++;
         if(!person[s2[i]])
            person[s2[i]] = size++;
    }
    size--;
    for(int i = 1 ; i <= size ; i++)
        G[i].clear();
    for(int i = 0 ; i < n - 1 ; i++){
         int x = person[s1[i]] , y = person[s2[i]];
         G[y].push_back(x);
    }
    return true;
}
void DP(int pos){
    if(G[pos].empty()){
        dp[pos][0] = 0;
        dp[pos][1] = 1;
        fp[pos][0] = 1; /*         */
        fp[pos][1] = 1;
        return ;
    }
    dp[pos][0] = 0;
    dp[pos][1] = 1;
    fp[pos][0] = 1;
    fp[pos][1] = 1;
    for(int i = 0 ; i < G[pos].size() ; i++){
        int son = G[pos][i];
        DP(son);
        if(fp[pos][1]){
        if(!fp[son][0]) /*             */
            fp[pos][1] = 0;
        }
        if(fp[pos][0]){
        if(dp[son][0] == dp[son][1]){
            fp[pos][0] = 0;
        }
        else if(dp[son][0] > dp[son][1] && !dp[son][0])
            fp[pos][0] = 0;
        else if(dp[son][1] > dp[son][0] && !dp[son][1])
            fp[pos][0] = 0;
        }
        dp[pos][1] += dp[son][0];
        dp[pos][0]  = dp[pos][0] + max(dp[son][1],dp[son][0]);
    }
    return ;
}
int main(){
    while(Input()){
        DP(1);
        if(dp[1][0] > dp[1][1]){
            printf("%d ",dp[1][0]);
            if(fp[1][0])
                printf("Yes");
            else
                printf("No");
        }
        else if(dp[1][0] < dp[1][1]){
            printf("%d ",dp[1][1]);
            if(fp[1][1])
                printf("Yes");
            else
                printf("No");
        }
        else{
            printf("%d ",dp[1][1]);
            printf("No");
        }
        printf("
");
    }
    return 0;
}