题目大意：
有n(n≤10000)台机器形成树形结构。要求在其中一些机器上安装服务器，使得每台不是服务器的计算机恰好和一台服务器计算机相邻。求服务器的最少数量。
/* 递归时分为3种情况 0表示，u为服务器，那么他的所有子节点可以为服务器也可以不为服务器 res+=min(dp[v][0],dp[v][1]); 1表示,u不为服务器，但是u的父节点为服务器，那么所有子节点都不能为服务器 res=sum(dp[v][2]); 2表示，u不为服务器，且u的父亲也不为服务器，那么u的子节点中只有一个为服务器，别的都不为服务器 dp[u][2]可以根据dp[u][1]遍历一次推得，dp[u][2]=min(dp[u][2],dp[u][1]-dp[v][2]+dp[v][0]) */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 10010 #define INF 10010 int n,dp[maxn][3],num,head[maxn]; struct node{ int to,pre; }e[maxn*2]; void Insert(int from,int to){ e[++num].to=to; e[num].pre=head[from]; head[from]=num; } int f(int now,int fa,int sta){ if(dp[now][sta]!=-1)return dp[now][sta]; int res=0; if(sta==0){ res=INF; int cnt=0; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to;cnt++; if(to==fa)continue; res=min(res,f(to,now,1)); } if(cnt==1&&fa!=-1)res=INF; } if(sta==1){ for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(to==fa)continue; res+=min(f(to,now,1),f(to,now,2)); } res++; } if(sta==2){ for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(to==fa)continue; res+=f(to,now,0); } } dp[now][sta]=res; return res; } int main(){ //freopen("Cola.txt","r",stdin); while(1){ memset(dp,-1,sizeof(dp)); memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); num=0; scanf("%d",&n); int x,y; for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); Insert(x,y); Insert(y,x); } printf("%d ",min(f(1,-1,0),f(1,-1,1))); int t; scanf("%d",&t); if(t==-1)return 0; } }