題意：  給定n個人，存在上下級關系，每個人只有一個上級，求最大獨立集。并判斷最大獨立集是否唯一     

  思路：d[i][0]表示以i為根的子樹中，不選擇第i個節(jié)點的最大獨立集，f[i][0]表示以i為根的子樹中，不選擇第i個節(jié)點的方案是否唯一。同理，d[i][1]和f[i][1]就是選擇第i個節(jié)點的情況。

  狀態(tài)轉移：d[i][0] =∑max(d[v][0], d[v][1]), d[i][1] = ∑d[v][0];

  唯一性的轉移方程見代碼：

if(k == 1) { //選擇節(jié)點u 			d[u][k] += dfs(v, 0); //不選擇子節(jié)點			if(!f[v][0]) f[u][k] = 0;  		}		else {			d[u][k] += max(dfs(v, 1), dfs(v, 0));			if(d[v][0] == d[v][1]) f[u][k] = 0;			else if(d[v][0] > d[v][1] && !f[v][0]) f[u][k] = 0;			else if(d[v][1] > d[v][0] && !f[v][1]) f[u][k] = 0;		}AC代碼：
#include<cstdio>#include<algorithm>#include<cstring>#include<utility>#include<string>#include<iostream>#include<map>#include<set>#include<vector>#include<queue>#include<stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 200 + 5;map<string, int>name;vector<int>son[maxn];int cnt, d[maxn][2], f[maxn][2];int getID(string &p) {	if(!name.count(p)) name[p] = cnt++;	return name[p];}int dfs(int u, int k) {	f[u][k] = 1;	d[u][k] = k;	int n = son[u].size();	for(int i = 0; i < n; ++i) {		int v = son[u][i];		if(k == 1) { //選擇節(jié)點u 			d[u][k] += dfs(v, 0); //不選擇子節(jié)點			if(!f[v][0]) f[u][k] = 0;  		}		else {			d[u][k] += max(dfs(v, 1), dfs(v, 0));			if(d[v][0] == d[v][1]) f[u][k] = 0;			else if(d[v][0] > d[v][1] && !f[v][0]) f[u][k] = 0;			else if(d[v][1] > d[v][0] && !f[v][1]) f[u][k] = 0;		}	}	return d[u][k];}int main() {	int n, root;	string boss, kid;	while(scanf("%d", &n) == 1 && n) {		for(int i = 0; i < n; ++i) son[i].clear();		name.clear();		cnt = 0;		cin >> boss;		getID(boss);		for(int i = 1; i < n; ++i) {			cin >> kid >> boss;			int par = getID(boss), kids = getID(kid);			son[par].push_back(kids);		}		int ans = max(dfs(0, 0), dfs(0, 1));		PRintf("%d ", ans);		int only = 1;		if(d[0][0] == d[0][1]) only = 0;		else if(d[0][0] > d[0][1] && !f[0][0]) only = 0;		else if(d[0][1] > d[0][0] && !f[0][1]) only = 0;		if(only) printf("Yes/n");		else printf("No/n");	}		return 0;}如有不當之處歡迎指出！