题目链接：?id=3342题目大意：一棵树，父亲和儿子不能同时选入同一个集合，现在求能选集合中元素个数最多的那个集合大小，并判断解是否唯一题目分析：求树的最大独立集的问题，好题，也用了两次dp的思想，有点类似HDU 5282这题的思想dp[i][0]表示不选第i个结点，集合大小的最大值dp[i][1]表示选第i个结点，集合大小的最大值对于此dp显然dp[i][1] = dp[son][0] 选父亲则不能选儿子dp[i][0] = max(dp[son][0], dp[son][1]) 不选父亲的话则值等于选儿子或者不选儿子里的较大值s[i][1] == true 表示选第i个结点时有唯一解，false表示解不唯一s[i][0] == true 表示不选第i个结点时有唯一解，false表示解不唯一开始时设s[i][1]，s[i][0]都为true，对于此dp，我们主要考虑父亲的解变成不唯一的情况与第一个dp状态对应，分成选父亲和不选父亲两种情况if(!s[son][0]) s[i][1] = false，，意思是如果不选儿子时有多个解，则此时可以选父亲，选父亲也肯定有多个解if(dp[son][0] == dp[son][1]) s[i][0] = false，如果选不选儿子的答案相同，显然不选父亲时有多个解，因为选不选儿子都可以最后自叶子向根回溯求解判断即可，这题因为map没清零，wa了大半天。。。#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <vector>#include <map>#include <iostream>using namespace std;int const MAX = 300;int n;int dp[MAX][2];bool s[MAX][2];bool vis[MAX];vector <int> vt[MAX];void DFS(int fa){dp[fa][1] = 1;vis[fa] = true;s[fa][0] = true;s[fa][1] = true;int sz = vt[fa].size();for(int i = 0; i < sz; i++){int son = vt[fa][i];if(!vis[son]){DFS(son);dp[fa][1] += dp[son][0];dp[fa][0] += max(dp[son][0], dp[son][1]);if(dp[son][0] == dp[son][1])s[fa][0] = false;if(!s[son][0])s[fa][1] = false;}}return;}int main(){while(scanf("%d", &n) != EOF && n){map <string, int> mp;for(int i = 0; i < MAX; i++)vt[i].clear();memset(vis, false, sizeof(vis));memset(dp, 0, sizeof(dp));int cnt = 0;string boss, fir, sec;cin >> boss;mp[boss] = cnt ++;for(int i = 0; i < n – 1; i++){cin >> sec >> fir;if(!mp.count(fir))mp[fir] = cnt ++;if(!mp.count(sec))mp[sec] = cnt ++;vt[mp[fir]].push_back(mp[sec]);}DFS(0);if(dp[0][1] > dp[0][0] && s[0][1])printf("%d Yes\n", dp[0][1]);else if(dp[0][1] < dp[0][0] && s[0][0])printf("%d Yes\n", dp[0][0]);elseprintf("%d No\n", max(dp[0][0] , dp[0][1]));}}
追寻爱情，然后发现，爱，从来就是一件千回百转的事。
