学步园

题意：n个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，求最多能选多少个人出来，并且求出获得最大人数的选人方案是否唯一。

思路：第一道树状DP，不太会，是按解题报告的思路写的。
地址：http://wenku.baidu.com/view/aee323cd0508763231121252.html 
也就不多解释了

//352K   
0MS
#include <stdio.h>
#include <string.h>
#define M 205

int dp[M][2],tree[M][M],unique[M][2];
char name[M][M/2];
int n,m;

int get_id (char str[])  //查询每个name 的位置
{
    int i;
    for (i = 0;i
< m;i ++)
    {
       
if (strcmp (str,name[i]) == 0)
           
return i;
    }
    if (i ==
m)       
//若没有则加进去
    {
       
strcpy (name[m++],str);
       
return i;
    }
    return
0;
}
int max (int a ,int b)
{
    return a
> b ? a : b;
}
void dfs (int fat)
{
    int num =
tree[fat][0];
    for (int i =
1;i <= num; i ++)
    {
       
int leaf = tree[fat][i];
       
dfs (leaf);
       
dp[fat][0] += max (dp[leaf][0],dp[leaf][1]);
       
dp[fat][1] += dp[leaf][0];
       
if (unique[leaf][0] ==
0)        
//判断唯一性
           
unique[fat][1] = 0;
       
if ((dp[leaf][0] >
dp[leaf][1]&&unique[leaf][0] ==
0)||(dp[leaf][0]<dp[leaf][1]&&unique[leaf][1]
== 0)
                
||dp[leaf][0] == dp[leaf][1])
                
unique[fat][0] = 0;
    }
}
int main ()
{
    int i;
    char
s1[M/2],s2[M/2];
    while
(scanf("%d",&n)&&n)

    {
       
memset (name,'\0',sizeof(name));
       
memset (dp,0,sizeof(dp));
       
memset (unique,0,sizeof(unique));
       
memset (tree,0,sizeof(tree));
       
m = 0;
       
for (i = 0;i < n;i ++)
       
{
           
dp[i][0] = 0;