// uva 1220 Patty at Hali-Bula // 树上最大独立集 + 最大独立集是否唯一// d[u][0] 表示不选该节点时的最大独立集// d[u][1] 表示选该节点时的最大独立集// d[u][0] = sigma max(d[v][0],d[v][1]){v是u的子节点}// d[u][1] = sigma d[v][0] // 分别表示没选该节点时，子节点任意// 选了该节点时，子节点就不能选//// 判断唯一，要稍微麻烦一点// f[u][0]表示没选该节点时的最大独立集是否唯一// f[u][1]表示选了该节点时的最大独立集是否唯一// 值为0，表示不唯一，值为1，表示唯一。// 则f[u][0] 为 1 的条件是，当d[v][0] != d[v][1] && 其中最大的那个// f[v][x]{x为d[v][0],d[v][1]中最大的那个第二维的标号}==1。// 而f[u][1]为 1 的条件是：所有的f[v][0]都等于1的时候才是唯一的//// 最后就是输入的时候有点麻烦，用到了map，其他的都还好//// 要不是开始的时候把数据看成只有100，RE了，之后可是1A呢//// 其实还是挺简单的，继续练吧。。。#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#include <string>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highbit(x) (1ull<<(63-__builtin_clzll(x)))#define popcount __builtin_popcountlltypedef long long ll;using namespace std;const int mod = 1000000007;const long double pi = acos(-1.l);template<class t> inline t lcm(const t& a, const t& b) { return a/gcd(a, b)*b; }template<class t> inline t lowbit(const t& x) { return x&-x; }template<class t> inline t maximize(t& a, const t& b) { return a=a<b?b:a; }template<class t> inline t minimize(t& a, const t& b) { return a=a<b?a:b; }const int maxn = 300;map<string,int> tab;int n;vector<int> mp[maxn];int d[maxn][2];int f[maxn][2];int cnt;void dfs(int u,int fa){d[u][1]=1;d[u][0] = 0;f[u][0] = 1;f[u][1] = 1;for (int i=0;i<mp[u].size();i++){int v = mp[u][i];dfs(v,u);d[u][0] += max(d[v][0],d[v][1]);if (d[v][0]==d[v][1])f[u][0] = 0;int x = (d[v][0]>d[v][1]) ? 0 : 1;if (f[v][x]==0)f[u][0] = 0;d[u][1] += d[v][0];if (f[v][0]==0)f[u][1] = 0 ; }}int main() {//freopen("g:\\code\\1.txt","r",stdin);while(scanf("%d",&n)!=eof){if (n==0)break;for (int i=0;i<n;i++)mp[i].clear();tab.clear();memset(d,0,sizeof(d));//memset(f,0,sizeof(f));cnt = 0;string a,b;cin>>a;tab[a] = cnt++;for (int i=1;i<n;i++){cin >> a >> b;if (tab.find(a)==tab.end()){tab[a] = cnt++;}if (tab.find(b)==tab.end()){tab[b] = cnt++;}mp[tab[b]].push_back(tab[a]);}dfs(0,-1);int ans = d[0][0];int flag = f[0][0];if (ans<d[0][1]){ans = d[0][1];flag = f[0][1];}if (d[0][0]==d[0][1]){flag = 0;}printf("%d ",ans);if (flag){puts("yes");}else {puts("no");}}return 0;}
，没有什么可留恋，只有抑制不住的梦想，
