好久没写树型dp了...以前都是先找到叶子节点.用队列维护来做的...这次学着vector动态数组+DFS回朔的方法..感觉思路更加的清晰...

关于题目的第一问...能邀请到的最多人数..so easy了...很基础的树形DP..dp[k][0]表示以k为根的子树不选k点时的最大人数...dp[k][1]代表选k点时的....

关键是题目要求判断是否最优解唯一...首先如果状态a可以转移到状态b并且状态a达到最优方案的方式不唯一....那么转移得到的b最优方案的方式也必然不唯一...那么可以用一个布尔型数组uni[k][tp] ( k代表哪个点,tp=0或者1..和dp里的意思一样...)来记录当前状态最优解是否唯一..转移的时候跟着转移...

如此一来..只要找到源头就可以了..设点p以及其父亲节点f

因为 dp[f][0] = dp[f][0] + max( dp[p][0] , dp[p][1] ) 并且f点若不使用,就不会再影响到更上层的点...所以若dp[p][0]==dp[p][1]..说明uni[f][0]=false..不唯一...

但是还要注意..最后的结果若dp[root][0]==dp[root][1]...就算uni[root][0]=true,unit[root][1]=true..方案也是不唯一的...这个很显然...

Program:

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<set>

#include<ctime>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define oo 1000000007

#define ll long long

#define pi acos(-1.0)

#define MAXN 205

using namespace std;

map<string,int> mymap;

vector<int> Tree[MAXN];

int n,dp[MAXN][2];

bool uni[205][2];

int ReadStringToInt(int &num)

{

      char str[105];

      string s;

      scanf("%s",str),s=str;

      if (!mymap.count(s)) mymap[s]=++num;

      return mymap[s];

}

void dfs(int x)

{

      int i,m=Tree[x].size();

      dp[x][0]=0,dp[x][1]=1;

      for (i=0;i<m;i++)

      {

             int p=Tree[x][i];

             dfs(p);

             if (dp[p][1] || dp[p][0])

             {

                  if (dp[p][1]>dp[p][0])

                  {

                         dp[x][0]+=dp[p][1];

                         if (!uni[p][1]) uni[x][0]=false;

                  }else

                  if (dp[p][0]>dp[p][1])

                  {

                         dp[x][0]+=dp[p][0];

                         if (!uni[p][0]) uni[x][0]=false;

                  }else

                         dp[x][0]+=dp[p][0],uni[x][0]=false;

             }

             if (dp[p][0])

             {

                  dp[x][1]+=dp[p][0];

                  if (!uni[p][0]) uni[x][1]=false;

             }

      }

      return;

}

int main()

{

      while (~scanf("%d",&n))

      {

             int i,num;

             if (!n) break;

             for (i=1;i<=n;i++) Tree[i].clear();

             mymap.clear();

             num=0;

             ReadStringToInt(num);

             for (i=1;i<n;i++)

             {

                    int ep,boss;

                    ep=ReadStringToInt(num);

                    boss=ReadStringToInt(num);

                    Tree[boss].push_back(ep);

             }

             memset(uni,true,sizeof(uni));

             dfs(1);

             printf("%d ",max(dp[1][0],dp[1][1]));

             bool f=true;

             if (dp[1][0]==dp[1][1]) f=false;

                else

             if (dp[1][0]>dp[1][1]) f=uni[1][0];

                else f=uni[1][1];

             if (f) printf("Yes\n");

                     else printf("No\n");

      }

      return 0;

}