1 /* 2    树形dp！ 3    判重思路： 4    当dp[v][0]==dp[v][1]时，很自然，flag[u][0]必然是有两种方案的。flag[u][1]则不然， 5    因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时，则必然flag[u][1]也不唯一 6    也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样)，那么父节点u不选的时候一定会有 7    多种方案！也就是flag[u][0]=false; 否则如果flag[v][0]==flase（子节点不选的时候有多种方案）, 8    那么父节点u选择的时候一定有多种方案，则flag[u][1]=false; 9 */10 #include<iostream>11 #include<cstring>12 #include<cstdio>13 #include<string>14 #include<map>15 #include<algorithm>16 #define N 20517 using namespace std;18 19 map<string, int>mp;20 int n;21 int cnt;22 int g[N][N];23 int dp[N][2];24 bool flag[N][2];25 map<string, int>::iterator it;26 27 void dfs(int u){28    for(int v=1; v<=n; ++v)29        if(g[u][v]){30           dfs(v);31           dp[u][1]+=dp[v][0];32           dp[u][0]+=max(dp[v][1], dp[v][0]);33           if(dp[v][1]==dp[v][0]) flag[u][0]=false;34           if(flag[v][0]==false) flag[u][1]=false;35        } 36 }37 38 int main(){39    string na1, na2;40    while(scanf("%d", &n) && n){41        mp.clear();42        memset(g, 0, sizeof(g));43        cnt=0;44        cin>>na1;45        mp[na1]=++cnt;46        for(int i=1; i<n; ++i){47            dp[i][1]=1;48            dp[i][0]=0;49            flag[i][1]=flag[i][0]=true;50            cin>>na1>>na2;51            it=mp.find(na1);52            if(it==mp.end())53               mp[na1]=++cnt;54            it=mp.find(na2);55            if(it==mp.end())56                mp[na2]=++cnt;57            g[mp[na2]][mp[na1]]=1; 58        }59        dp[n][1]=1;60        dp[n][0]=0;61        flag[n][1]=flag[n][0]=true;62        dfs(1); 63        if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s\n", dp[1][1], "Yes");64        else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s\n", dp[1][0], "Yes");65        else printf("%d %s\n", max(dp[1][0], dp[1][1]), "No");66    }67    return 0;68 }