hdu2412 Party at HaliBula

http://acm.hdu.edu.cn/showproblem.php?pid=2412

树状DP，找出树中互不相邻的点，最多能有多少个，判断是否唯一比较麻烦

不涂即为白色，黑色表示选择该点

不唯一的涂色方法可以分为以下两种树：

1.(如果根节点为白色，最多的涂色方法)dp[i][0] 有多种的树

2.(如果根节点为黑色，最多的涂色方法)dp[i][1] 有多种的树

形成1类型树方法：

如果根节点为白色，它的子树中有任意一个满足下面条件：

dp[j][0] == dp[j][1]

或（dp[j][0] > dp[j][1] 且该子树为1类型树）

或（dp[j][1] > dp[j][0] 且该子树为2类型树）

形成2类型树方法：

如果根节点为白色，它的子树中有任意一个是1类型树：

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string>
  4 #include <vector>
  5 #include <map>
  6 
  7 using namespace std;
  8 
  9 vector<int> p[210];
 10 vector<int>::iterator it;
 11 int n, dp[210][2], mark[210][2];
 12 
 13 void dfs(int x)
 14 {
 15     int i, j, sum1, sum2;
 16     if(p[x].empty())
 17     {
 18         dp[x][0] = 0;
 19         dp[x][1] = 1;
 20         mark[x][0] = mark[x][1] = 0;
 21         return;
 22     }
 23     sum1 = 0; //don't choose
 24     sum2 = 1; //choose
 25     for(i=0; i<p[x].size(); i++)
 26     {
 27         j = p[x][i];
 28         dfs(j);
 29         if(dp[j][1] > dp[j][0] && mark[j][1])
 30         {
 31             mark[x][0] = 1;
 32         }
 33         if(dp[j][0] > dp[j][1] && mark[j][0])
 34         {
 35             mark[x][0] = 1;
 36         }
 37         if(dp[j][0] == dp[j][1])
 38         {
 39             mark[x][0] = 1;
 40         }
 41         if(mark[j][0])
 42         {
 43             mark[x][1] = 1;
 44         }
 45         sum1 += max(dp[j][0], dp[j][1]);
 46         sum2 += dp[j][0];
 47     }
 48     dp[x][0] = sum1;
 49     dp[x][1] = sum2;
 50 }
 51 
 52 int main()
 53 {
 54     string s, s1, s2;
 55     map<string, int> map1;
 56     int i, temp1, temp2;
 57     while(scanf("%d", &n), n)
 58     {
 59         for(i=1; i<=n; i++)
 60         {
 61             mark[i][0] = mark[i][1] = 0;
 62             p[i].clear();
 63         }
 64         map1.clear();
 65         cin >> s;
 66         map1.insert(make_pair(s, 1));
 67         i = 2;
 68         n = n - 1;
 69         while(n-- && cin >> s1 >> s2)
 70         {
 71             if(map1.find(s1) == map1.end())
 72             {
 73                 map1.insert(make_pair(s1, i));
 74                 i = i + 1;
 75             }
 76             if(map1.find(s2) == map1.end())
 77             {
 78                 map1.insert(make_pair(s2, i));
 79                 i = i + 1;
 80             }
 81             temp1 = map1[s1];
 82             temp2 = map1[s2];
 83             p[temp2].push_back(temp1);
 84         }
 85         dfs(1);
 86         if(dp[1][0] == dp[1][1])
 87         {
 88             printf("%d No\n", dp[1][0]);
 89             continue;
 90         }
 91         if(dp[1][0] > dp[1][1])
 92         {
 93             printf("%d ", dp[1][0]);
 94             printf(mark[1][0]? "No\n": "Yes\n");
 95             continue;
 96         }
 97         if(dp[1][0] < dp[1][1])
 98         {
 99             printf("%d ", dp[1][1]);
100             printf(mark[1][1]? "No\n": "Yes\n");
101         }
102     }
103     return 0;
104 }