题意是挑选尽量多的人，并且每个人都不和他的父节点同时出现，很明显的最大独立集问题，难点在于如何判断方案是否唯一。
详情请见刘汝佳《算法竞赛入门经典--第二版》P282
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
#define INF 1e6
using namespace std;
const int maxn = ; char ch[],fa[];
char trie[maxn][];
int k;
int d[maxn][],f[maxn][];
vector<int> g[maxn]; int ID(char *s)//给每个字符串分配ID；
{
int i = ;
for(i = ; i < k; ++i)
{
if(strcmp(s,trie[i]) == ) {
return i;
}
}
if(i == k) strcpy(trie[k],s);
k++;
return k-;
}
int dp(int u,int x)
{
if(d[u][x]!=-) return d[u][x];//记忆化
if(x == ){
int sum = ;
f[u][] = ;
if(g[u].size() == ) return d[u][] = ;
for(int i = ; i < g[u].size(); ++i)
{
sum+=dp(g[u][i],);
if(f[g[u][i]][] == ) {
f[u][] = ;
}
}
return d[u][] = sum;
}
else
{
int sum = ;
f[u][] = ;
if(g[u].size() == ) return d[u][] = ;
for(int i = ; i < g[u].size(); ++i)
{
int p = dp(g[u][i],),q = dp(g[u][i],);
if(p == q)
{
sum+=p;
f[u][] = ;
}
else if(p > q)
{
sum+=p;
if(f[g[u][i]][] == ) f[u][] = ;
}
else if(p < q)
{
sum+=q;
if(f[g[u][i]][] == ) f[u][] = ;
}
}
return d[u][] = sum;
}
}
int main()
{
//freopen("in","r",stdin);
int n;
while(~scanf("%d",&n)&&n)
{
int from,to;
k = ;
scanf("%s",ch);
ID(ch);//big boss是0号
for(int i = ; i < n; ++i)
{
scanf("%s%s",ch,fa);
from = ID(ch);
to = ID(fa);
g[to].push_back(from);
}
//printf("%d\n",g[0].size());
memset(d,-,sizeof(d));
dp(,);
dp(,);
if(d[][] > d[][])
{
printf("%d ",d[][]);
if(f[][]) puts("Yes");
else puts("No");
}
else if(d[][] < d[][])
{
printf("%d ",d[][]);
if(f[][]) puts("Yes");
else puts("No");
}
else
{
printf("%d ",d[][]);
puts("No");
}
for(int i = ; i < n; ++i) g[i].clear(); }
}