题目大意：给出一棵树，，在某个选择某个结点可以覆盖和它相连的所有边，问最少选多少个结点所有边都被覆盖。
首先将无根树转化为有根树，0为根。
用d[i][0]表示不选择结点i时覆盖以结点i为根的子树最少要多少个结点，用d[i][1]表示选择结点i时覆盖以结点i为根的子树最少要多少个结点。若结点i不选，为了和覆盖所有和结点i相连的结点，则每个儿子都必须选，若结点i选，则每个儿子选择较小的那个值。按DFS顺序递推。
状态转移方程：
d[i][0]=sum { d[u][1] }（u是i的儿子）
d[i][1]=sum { min { d[u][0],d[u][1] } }+1（u是i的儿子）
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<vector>using namespace std;int a[30];int d[1510][2];char e[1510];int par[1510];vector<int> G[1510];void dfs(int u);void rootedtree(int u,int fa);int main(void){int i,j,u,n,sump,top,lo;while(scanf("%d",&n)==1){for(i=0;i<n;i++){G[i].clear();}for(i=1;i<=n;i++){scanf("%s",e);lo=strlen(e);j=top=0;while(j<lo){if((e[j]>='0')&&(e[j]<='9')){sump=0;while((e[j]>='0')&&(e[j]<='9')){sump=sump*10+e[j]-'0';j++;}top++;a[top]=sump;}else{j++;}}for(j=1;j<=a[2];j++){scanf("%d",&u);G[a[1]].push_back(u);G[u].push_back(a[1]);}}rootedtree(0,-1);for(i=0;i<n;i++){G[i].clear();}for(i=1;i<n;i++){G[par[i]].push_back(i);}dfs(0);printf("%d\n",d[0][0]>d[0][1]?d[0][1]:d[0][0]);}return 0;}void dfs(int u){int i,p,minp,sump;p=G[u].size();if(p==0){d[u][0]=0;d[u][1]=1;}else{for(i=0;i<p;i++){dfs(G[u][i]);}sump=minp=0;for(i=0;i<p;i++){minp=minp+(d[G[u][i]][0]>d[G[u][i]][1]?d[G[u][i]][1]:d[G[u][i]][0]);sump=sump+d[G[u][i]][1];}d[u][0]=sump;d[u][1]=minp+1;}}void rootedtree(int u,int fa){int i,v,p;p=G[u].size();for(i=0;i<p;i++){v=G[u][i];if(v!=fa){par[v]=u;rootedtree(v,u);}}}
也有伤心的，既有令人兴奋的，也有令人灰心的，
