题意：一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，，
问把所有边看守住最少需要放多少士兵。
思路：和最大独立集的思路差不多，转移方程差不多，用0，1表示子树的根放不放士兵
dp[root][0] += dp[son][1];
dp[root][1] += min(dp[son][1],dp[son][0]);
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<vector>using namespace std;const int N = 1500+100;int n;char op[25];int dp[N][2];struct node{int to;int next;}es[N<<1];int head[N];void dfs(int u,int pa){dp[u][1]=1;for(int i=head[u];~i;i=es[i].next){int v=es[i].to;if(v==pa) continue;dfs(v,u);dp[u][0]+=dp[v][1];dp[u][1]+=min(dp[v][1],dp[v][0]);}}int main(){while(~scanf("%d",&n)){int root=-1;int top=0;memset(dp,0,sizeof(dp));memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){int s=0,m;scanf("%d:(%d)",&s,&m);if(root==-1) root=s;for(int i=1;i<=m;i++){int v;scanf("%d",&v);es[top].to=v;es[top].next=head[s];head[s]=top++;es[top].to=s;es[top].next=head[v];head[v]=top++;}}dfs(root,-1);printf("%d\n",min(dp[root][1],dp[root][0]));}return 0;}
勇于接受自己的不完美，认清自己不足的地方，
