题意：
有一棵树，选出尽可能多的节点是的两两节点不相邻，即每个节点和他的子节点只能选一个。求符合方案的最大节点数，并最优方案判断是否唯一。
分析：
d(u, 0)表示以u为根的子树中，不选u节点能得到的最大人数，f(u, 0)表示方案是否唯一。
d(u, 1)表示选u节点能得到的最大人数，同理，f(u, 1)表示方案是否唯一。
状态的转移：
- d(u, 1)的计算：因为选了u节点，所以u的子节点都不能选。d(u, 1) = sum{ d(v, 0) | v是u的子节点 }
- f(u, 1)的计算：当且仅当f(v, 0) == 1时，f(u, 1)才是1
- d(u, 0)的计算：因为没有选u节点，所以对于每个子节点v可选可不选。d(u, 0) = sum{ max(d(v, 0), d(v, 1)) }
- f(u, 0)的计算：方案不唯一有两种情况，某个d(v, 1) == d(v, 0) 或者 对应取到max方案的f为1
这里用了C++中的map，将字符串与编号对应起来，编写代码比较方便。
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std; const int maxn = ;
vector<int> sons[maxn];
map<string, int> dict;
int cnt, d[maxn][], f[maxn][]; int ID(const string& s)
{
if(!dict.count(s)) dict[s] = cnt++;
return dict[s];
} int dp(int u, int k) {
f[u][k] = ;
d[u][k] = k;
for(int i = ; i < sons[u].size(); i++) {
int v = sons[u][i];
if(k == ) { //选节点u
d[u][] += dp(v, );
if(!f[v][]) f[u][] = ; //如果子节点v不唯一，则父节点u也不唯一
} else {
d[u][] += max(dp(v, ), dp(v, ));
if(d[v][] == d[v][]) f[u][k] = ;
else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;
else if(d[v][] > d[v][] && !f[v][]) f[u][k] = ;
}
}
return d[u][k];
} int main(void)
{
#ifdef LOCAL
freopen("1220in.txt", "r", stdin);
#endif int n;
string s, s2;
while(cin >> n >> s)
{
getchar();
cnt = ;
dict.clear();
for(int i = ; i <= n; ++i) sons[i].clear(); //cin >> s;
ID(s);
for(int i = ; i < n; ++i)
{
cin >> s >> s2;
sons[ID(s2)].push_back(ID(s));
}
printf("%d ", max(dp(, ), dp(, )) );
bool unique = false;
if(d[][] > d[][] && f[][]) unique = true;
if(d[][] > d[][] && f[][]) unique = true;
printf("%s\n", unique ? "Yes" : "No");
} return ;
}
代码君