对于一颗n个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集），然后输入n-1条无向边，输出一个最大独立集（如果有多解输出任意一组）。
任选一个根r，d(i)表示以i为根结点的子树的最大独立集大小，结点i有两种决策，选与不选，如果不选i，问题变成了所有儿子的值相加，如果选i,问题变成了所有孙子的值相加再加1，即d(i)=max(1+Σd(j)，Σd(k));j为i的孙子(gs[i])，k为i的儿子(s[i])。实现时可以从s[i]与gs(i)的元素去找i，即当计算出一个d(i)后，用它去更新其父亲结点和祖父结点的累加值。(以上来自紫书)。-关于UVA 1220 Party at Hali-Bula：d(i,0)表示以i为根结点的子树在选择i的情况下的最大独立集，d(i,1)表示以i为根结点的子树在不选择i的情况下的最大独立集，则有d(i,1)=Σmax(d(s[i],0),d(s[i],1));d(i,0)=Σd(s[i],1);关于方案的唯一性（自上而下考虑更容易），在选择i点时其所有儿子唯一i才唯一，不选择i的情况下如果d(s[i],0)=d(s[i],1)或者两者max的那一项不唯一i才不唯一； #include<iostream> #include<cstring> #include<cstdio> #include<map> #include<fstream> using namespace std; int d[205][2],n,num,tmp;//0:取,1：不取 bool onl[205][2],used[205];//1:不唯一 struct tree{ int s,f; }t[205]; int main() { // freopen("1.txt","w",stdout); while(cin>>n&&n) { string s1,s2; num=0; map<int,string>m; map<string,int>q; cin>>s1; m[++num]=s1; q[s1]=1; for(int i=1;i<n;i++) { cin>>s1>>s2; if(!q[s1]) { m[++num]=s1; q[s1]=num; } if(!q[s2]) { m[++num]=s2; q[s2]=num; } t[q[s2]].s+=1; t[q[s1]].f=q[s2]; } tmp=n; for(int i=1;i<=n;i++) d[i][0]=1; while(tmp!=0) { for(int i=1;i<=n;i++) { if(!t[i].s&&!used[i]) { used[i]=1; tmp--; t[t[i].f].s--; if(t[i].f) { if(d[i][0]==d[i][1]) onl[t[i].f][1]=1; if(d[i][0]>d[i][1]&&onl[i][0]||d[i][0]<d[i][1]&&onl[i][1]) onl[t[i].f][1]=1; if(onl[i][1]) onl[t[i].f][0]=1; d[t[i].f][1]+=max(d[i][0],d[i][1]); d[t[i].f][0]+=d[i][1]; } } } } if(d[1][0]>d[1][1]) cout<<d[1][0]<<' '<<(onl[1][0]==1?"No":"Yes")<<endl; else if(d[1][0]<d[1][1]) cout<<d[1][1]<<' '<<(onl[1][1]==1?"No":"Yes")<<endl; else cout<<d[1][1]<<' '<<"No"<<endl; memset(t,0,sizeof(t)); memset(used,0,sizeof(used)); memset(onl,0,sizeof(onl)); memset(d,0,sizeof(d)); } return 0; }