dp[u][0]表示不选u时在以u为根的子树中最大人数，dp[u][1]则是选了u后的最大人数；
f[u][0]表示不选u时的唯一性，f[u][1]是选了u后的唯一性，值为1代表唯一，0代表不唯一。
当不选u时，u的子节点v可选可不选，dp[u][0]+=max(dp[v][0],dp[v][1]),再根据所选判断f[u][0]；
当选u时，u的子节点都不可选，dp[u][1]+=dp[v][0],再判断f[u][1]；
在这里可以用map将人名映射为数字，map<string,int> mp 。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<string>
5 #include<cstring>
6 #include<map>
7 #include<vector>
8 using namespace std;
9 int dp[210][2],f[210][2];
10 vector<int>E[210];
11
12 void dfs(int u){
13 dp[u][0]=0;
14 dp[u][1]=1;
15 for(int i=0;i<E[u].size();i++){
16 int v=E[u][i];
17 dfs(v);
18 if(dp[v][0]==dp[v][1]){
19 dp[u][0]+=dp[v][0];
20 f[u][0]=0;
21 }
22 else if(dp[v][0]>dp[v][1]){
23 dp[u][0]+=dp[v][0];
24 if(!f[v][0]) f[u][0]=0;
25 }
26 else{
27 dp[u][0]+=dp[v][1];
28 if(!f[v][1]) f[u][0]=0;
29 }
30 dp[u][1]+=dp[v][0];
31 if(!f[v][0]) f[u][1]=0;
32 }
33 }
34
35 int main(){
36 int n,k;
37 string s1,s2;
38 map<string,int> mp;//将字符串映射为数字
39 while(cin>>n&&n){
40 mp.clear();
41 for(int i=0;i<=n;i++) E[i].clear(); //清空
42 memset(f,1,sizeof(f));//初始都设为唯一
43 k=1;
44 cin>>s1;
45 mp[s1]=k++;
46 E[0].push_back(mp[s1]);//增加超根
47 for(int i=1;i<=n-1;i++){
48 cin>>s1>>s2;
49 if(mp[s1]==0) mp[s1]=k++;
50 if(mp[s2]==0) mp[s2]=k++;
51 E[mp[s2]].push_back(mp[s1]);
52 }
53 dfs(0);//从根开始遍历
54 printf("%d ",dp[0][0]);
55 if(f[0][0]) printf("Yes\n");
56 else printf("No\n");
57 }
58 return 0;
59 }
