1 /* 2 樹形dp！ 3 判重思路： 4 當dp[v][0]==dp[v][1]時，很自然，flag[u][0]必然是有兩種方案的。flag[u][1]則不然， 5 因為它只和dp[v][0]有關系。而若flag[v][0]不唯一時，則必然flag[u][1]也不唯一 6 也就是u的子節點有dp[v][1]==dp[v][0](選與不選都一樣)，那么父節點u不選的時候一定會有 7 多種方案！也就是flag[u][0]=false; 否則如果flag[v][0]==flase（子節點不選的時候有多種方案）, 8 那么父節點u選擇的時候一定有多種方案，則flag[u][1]=false; 9 */ 10 #include<iostream> 11 #include<cstring> 12 #include<cstdio> 13 #include<string> 14 #include<map> 15 #include<algorithm> 16 #define N 205 17 using namespace std; 18 19 map<string, int>mp; 20 int n; 21 int cnt; 22 int g[N][N]; 23 int dp[N][2]; 24 bool flag[N][2]; 25 map<string, int>::iterator it; 26 27 void dfs(int u){ 28 for(int v=1; v<=n; ++v) 29 if(g[u][v]){ 30 dfs(v); 31 dp[u][1]+=dp[v][0]; 32 dp[u][0]+=max(dp[v][1], dp[v][0]); 33 if(dp[v][1]==dp[v][0]) flag[u][0]=false; 34 if(flag[v][0]==false) flag[u][1]=false; 35 } 36 } 37 38 int main(){ 39 string na1, na2; 40 while(scanf("%d", &n) && n){ 41 mp.clear(); 42 memset(g, 0, sizeof(g)); 43 cnt=0; 44 cin>>na1; 45 mp[na1]=++cnt; 46 for(int i=1; i<n; ++i){ 47 dp[i][1]=1; 48 dp[i][0]=0; 49 flag[i][1]=flag[i][0]=true; 50 cin>>na1>>na2; 51 it=mp.find(na1); 52 if(it==mp.end()) 53 mp[na1]=++cnt; 54 it=mp.find(na2); 55 if(it==mp.end()) 56 mp[na2]=++cnt; 57 g[mp[na2]][mp[na1]]=1; 58 } 59 dp[n][1]=1; 60 dp[n][0]=0; 61 flag[n][1]=flag[n][0]=true; 62 dfs(1); 63 if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s\n", dp[1][1], "Yes"); 64 else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s\n", dp[1][0], "Yes"); 65 else printf("%d %s\n", max(dp[1][0], dp[1][1]), "No"); 66 } 67 return 0; 68 }
?
)
