/*
树形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][];
bool flag[N][];
map<string, int>::iterator it; void dfs(int u){
for(int v=; v<=n; ++v)
if(g[u][v]){
dfs(v);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][], dp[v][]);
if(dp[v][]==dp[v][]) flag[u][]=false;
if(flag[v][]==false) flag[u][]=false;
}
} int main(){
string na1, na2;
while(scanf("%d", &n) && n){
mp.clear();
memset(g, , sizeof(g));
cnt=;
cin>>na1;
mp[na1]=++cnt;
for(int i=; i<n; ++i){
dp[i][]=;
dp[i][]=;
flag[i][]=flag[i][]=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]]=;
}
dp[n][]=;
dp[n][]=;
flag[n][]=flag[n][]=true;
dfs();
if(dp[][]>dp[][] && flag[][]) printf("%d %s\n", dp[][], "Yes");
else if(dp[][]>dp[][] && flag[][]) printf("%d %s\n", dp[][], "Yes");
else printf("%d %s\n", max(dp[][], dp[][]), "No");
}
return ;
}
05-11 16:59
查看更多