UVa 1220 Hali-Bula的晚会（树的最大独立集）

题意：

公司里有n个人形成一个树状结构，即除了老板以外每个员工都有唯一的直属上司。要求选尽量多的人，但不能同时选择一个人和他的直属上司。输出最多能选多少人并判断是否唯一。

思路：

树的最大独立集问题。就是需要额外判定是否是唯一的。

因为输入的都是人名，所以首先就是用map容器来处理，上下属的关系就用vector容器来处理。

d[u][1]表示以u为根的子树中，选u点能得到的最大人数，f[u][1]判断这种方案是否唯一。

d[u][0]表示以u为根的子树中，不选u点能得到的最大人数，f[u][0]判断这种方案是否唯一。

状态转移方程其实不是很难。首先分析d[u][1]，因为u选了，所以u的子结点都不能选，它的子节点的状态只能是这样的，所以此时d[u][1]=sum（d[v][0]|v是u的子节点）。容易想到f[v][0]都为唯一时，f[u][1]才是唯一的。

其次是d[u][0]，此时u的子节点可选可不选，所以我们需要挑选出更大的那个，每个子节点都是这样处理，最后像上面那样加起来就可以了。转移方程就是d[u][0]=sum(max(d[v][0],d[v][1]))。方案唯一值的判定和上面是一样的，就是分析你所挑选的更大的那个。

根结点值依赖于子节点，所以需要用DFS来处理。

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 #include<map>

 using namespace std;

 const int maxn = +;

 int n, cnt;

 string s1, s2;

 int d[maxn][], f[maxn][];

 map<string, int> id;

 vector<int> sons[maxn];

 void solve(int u)

 {

     //最下属的只有两种情况

     if (sons[u].size() == )

     {

         d[u][] = ;

         d[u][] = ;

         return;

     }

     int k = sons[u].size();

     for (int i = ; i < k; i++)

     {

         int son = sons[u][i];

         //树形的DFS

         solve(son);

         d[u][] += d[son][];

         //一旦有子节点不唯一，它也不唯一

         if (!f[son][])    f[u][] = ;

         //u不选时，它的子节点可选可不选，此时需要选个大的

         d[u][] += max(d[son][], d[son][]);

         //判断是否唯一

         if (d[son][]>d[son][] && !f[son][])             f[u][] = ;

         else if (d[son][] > d[son][] && !f[son][] )     f[u][] = ;

         else if (d[son][] == d[son][])                   f[u][] = ;

     }

     ++d[u][];

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     while (cin >> n && n)

     {

         memset(d, , sizeof(d));

         //初始化都为唯一

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

             f[i][] = f[i][] = ;

         id.clear();

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

             sons[i].clear();

         cnt = ;

         cin >> s1;

         id[s1] = ++cnt;

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

         {

             cin >> s1 >> s2;

             if (!id[s1])  id[s1] = ++cnt;

             if (!id[s2])  id[s2] = ++cnt;

             sons[id[s2]].push_back(id[s1]);

          }

         solve();

         if (d[][] == d[][])  printf("%d No\n", d[][]);

         else if (d[][] > d[][])  printf("%d %s\n", d[][], !f[][] ? "No" : "Yes");

         else  printf("%d %s\n", d[][], !f[][] ? "No" : "Yes");

     }

     return ;

 }