POJ 3342 Party at Hali-Bula ——（树型DP）

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 using namespace std;
 9 const int N = 200 + 5;
10 
11 int n;
12 map<string,int> M;
13 vector<int> G[N];
14 int tot = 0;
15 int dp[N][2];
16 void dfs(int u)
17 {
18     dp[u][0] = 0;
19     dp[u][1] = 1;
20     for(int i=0;i<G[u].size();i++)
21     {
22         int v = G[u][i];
23         dfs(v);
24         dp[u][0] += max(dp[v][1], dp[v][0]);
25         dp[u][1] += dp[v][0];
26     }
27 }
28 
29 int main()
30 {
31     while(scanf("%d",&n) == 1 && n)
32     {
33         for(int i=1;i<=n;i++) G[i].clear();
34         tot = 0;
35         M.clear();
36         
37         string boss;
38         cin >> boss;
39         M[boss] = ++tot;
40         for(int i=1;i<n;i++)
41         {
42             string a,b;
43             cin >> a >> b;
44             if(M[a] == 0) M[a] = ++tot;
45             if(M[b] == 0) M[b] = ++tot;
46             int u = M[a], v = M[b];
47             G[v].push_back(u);
48         }
49         
50         dfs(1);
51         printf("%d ",max(dp[1][0], dp[1][1]));
52         int flag = dp[1][0] != dp[1][1];
53         for(int i=1;i<=n&&flag;i++)
54         {
55             if(dp[i][0] < dp[i][1]) continue;
56             for(int j=0;j<G[i].size()&&flag;j++)
57             {
58                 int v = G[i][j];
59                 if(dp[v][1] == dp[v][0])
60                 {
61                     flag = 0;
62                     break;
63                 }
64             }
65         }
66         puts(flag ? "Yes" : "No");
67     }
68     return 0;
69 }