链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3661
题意：
公司里有n（n≤200）个人形成一个树状结构，即除了老板之外每个员工都有唯一的直属上司。
要求选尽量多的人，但不能同时选择一个人和他的直属上司。问：最多能选多少人，以及在人数最多的前提下方案是否唯一。
分析：
本题几乎就是树的最大独立集问题，不过多了一个要求：判断唯一性。
一、设d(u,0)和f(u,0)表示以u为根的子树中，不选u点能得到的最大人数以及方案唯一性（f(u,0)=1表示唯一，0表示不唯一）。
二、设d(u,1)和f(u,1)表示以u为根的子树中，选u点能得到的最大人数以及方案唯一性。相应地，状态转移方程也有两套。
三、d(u,1)的计算：因为选了u，所以u的子结点都不能选，故d(u,1) = sum{d(v,0) | v是u的子结点}。当所有f(v,0)=1时f(u,1)=1。
四、d(u,0)的计算：因为u没有选，所以每个子结点v可选可不选，即d(u,0) = sum{ max(d(v,0), d(v,1)) }。
什么情况下方案是唯一的呢？首先，如果某个d(v,0)和d(v,1)相等，则不唯一；
其次，如果max取到的那个值对应的f=0，方案也不唯一（如d(v,0) > d(v,1) 且f(v,0)=0，则f(u,0)=0）。
代码：
#include <cstdio>
#include <map>
#include <string>
#include <vector>
using namespace std; const int UP = + ;
int cid, d[UP][]; // d数组表示以f为根的子树中，选或不选f点能得到的最大人数
bool u[UP][]; // u数组表示以f为根的子树中，选或不选f点的方案唯一性
map<string, int> M;
vector<int> son[UP]; int id(char* s){
if(M.count(s)) return M[s];
return M[s] = cid++;
} int dp(int f, int p){
d[f][p] = p;
u[f][p] = true;
for(int i = ; i < son[f].size(); i++){
int b = son[f][i];
if(p == ){
d[f][] += dp(b, );
if(!u[b][]) u[f][] = false;
}
else{
d[f][] += max(dp(b, ), dp(b, ));
if(d[b][] == d[b][]) u[f][] = false;
else if(d[b][] > d[b][] && !u[b][]) u[f][] = false;
else if(d[b][] > d[b][] && !u[b][]) u[f][] = false;
}
}
return d[f][p];
} int main(){
int n;
char f[], b[];
while(scanf("%d", &n) && n){
cid = ; M.clear();
for(int i = ; i < n; i++) son[i].clear(); scanf("%s", f); id(f);
for(int i = ; i < n; i++){
scanf("%s%s", b, f);
son[id(f)].push_back(id(b));
} printf("%d ", max(dp(, ), dp(, )));
bool ok = (d[][]>d[][]&&u[][]) || (d[][]>d[][]&&u[][]);
printf("%s\n", ok ? "Yes" : "No");
}
return ;
}