http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105116#problem/H
紫书P282
员工和直属老板只能选一个，最多选多少人
思路：d(u,0)表示以U为根的子树，不选u点，则子节点可选可不选，f(u,0)表示不选u的唯一性 （1表示唯一，0,表示不唯一）
d(u,1)以u为根的子树，选择u点，f(u,1)表示选择u的唯一性
转移方程：d(u,0) = sum{ max( d(v,0), d(v,1) ) }，v是子节点，当d(v,0) == d(v,1) ，不唯一，或者选择的那个不唯一，则f（u,0)不唯一
d(u,1) = sum{ d(v,0) }， 当f(v,0)有一个不唯一，则不唯一
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
const int MAX = ;
vector <int> son[MAX];
map<string, int> name;
int d[MAX][],f[MAX][];
void DP(int u)
{
if(son[u].size() == )
{
d[u][] = f[u][] = ;
d[u][] = ;
f[u][] = ;
return;
}
int c = (int) son[u].size();
for(int i = ; i < c; i++)
{
DP(son[u][i]);
}
int sum = ,flag = ;
for(int i = ; i < c; i++)
{
sum += d[ son[u][i] ][];
if(f[ son[u][i] ][] == )
flag = ;
}
if(flag)
f[u][] = ;
else
f[u][] = ;
d[u][] = max(d[u][], sum + );
sum = ,flag = ;
for(int i = ; i < c; i++)
{
if(d[ son[u][i] ][] > d[ son[u][i] ][])
{
sum += d[ son[u][i] ][] ;
if(f[ son[u][i] ][] == )
flag = ;
}
else if(d[ son[u][i] ][] < d[ son[u][i] ][])
{
sum += d[ son[u][i] ][];
if(f[ son[u][i] ][] == )
flag = ;
}
else
{
sum += d[ son[u][i] ][];
flag = ;
}
}
if(flag)
f[u][] = ;
else
f[u][] = ;
d[u][] = max(d[u][], sum);
}
int main()
{
int n,m;
char worker[],boss[];
while(scanf("%d", &n) != EOF && n)
{
for(int i = ; i < MAX; i++)
son[i].clear();
name.clear();
memset(d, , sizeof(d));
memset(f, , sizeof(f));
m = ;
scanf("%s", boss);
name[boss] = m++;
for(int i = ; i < n; i++)
{
scanf("%s%s",worker,boss);
if(name.count(worker) == ) //注意输入的处理
name[worker] = m++;
if(name.count(boss) == )
name[boss] = m++;
son[ name[boss] ].push_back( name[worker] );
}
DP();
if(d[][] > d[][])
{
printf("%d ", d[][]);
if(f[][])
printf("Yes\n");
else
printf("No\n");
}
else if(d[][] < d[][])
{
printf("%d ", d[][]);
if(f[][])
printf("Yes\n");
else
printf("No\n");
}
else
{
printf("%d ", d[][]);
printf("No\n");
}
}
return ;
}