思路:对于最大的人数很容易想到,就直接dp。但对于最大值是否唯一就需要应用辅助数组,isOnly[i][0]表示dp[i][0]是否唯一,同理isOnly[i][1]。
那么当(dp[v][0]>dp[v][1]&&isOnly[v][0]==0)或(dp[v][1]>dp[v][0]&&isOnly[v][1]==0)或(dp[v][1]==dp[v][0]),那么isOnly[u][0]=0;
如果isOnly[v][0]==0,那么isOnly[u][1]=0;
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#define Maxn 210
using namespace std;
int vi[Maxn],dp[Maxn][],n,isOnly[Maxn][];
vector <int> head[Maxn];
map <string,int> q;
void init()
{
memset(vi,,sizeof(vi));
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
head[i].clear();
q.clear();
}
void add(int u,int v)
{
head[u].push_back(v);
head[v].push_back(u);
}
void dfs(int u)
{
int i,v,sz;
vi[u]=;
sz=head[u].size();
dp[u][]=;
dp[u][]=;
isOnly[u][]=isOnly[u][]=;
for(i=;i<sz;i++)
{
v=head[u][i];
if(vi[v]) continue;
dfs(v);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][],dp[v][]);
if(dp[v][]>dp[v][]&&isOnly[v][]==) isOnly[u][]=;
else if(dp[v][]>dp[v][]&&isOnly[v][]==) isOnly[u][]=;
else if(dp[v][]==dp[v][]) isOnly[u][]=;
if(isOnly[v][]==) isOnly[u][]=;
}
}
int main()
{
int i,j,cnt=;
char str1[Maxn],str2[Maxn];
while(scanf("%d",&n),n)
{
cnt=;
init();
scanf("%s",&str1);
q[str1]=++cnt;
for(i=;i<n;i++)
{
scanf("%s%s",&str1,&str2);
if(!q[str1])
q[str1]=++cnt;
if(!q[str2])
q[str2]=++cnt;
add(q[str1],q[str2]);
}
dfs();
if(dp[][]>dp[][]&&isOnly[][])
printf("%d Yes\n",dp[][]);
else
if(dp[][]>dp[][]&&isOnly[][])
printf("%d Yes\n",dp[][]);
else
printf("%d No\n",max(dp[][],dp[][]));
}
return ;
}