问题描述
给定一个由N台计算机组成的树状网络，每台计算机可以选择作为服务器或客户端。服务器可以服务其所有相邻的客户端，但每个客户端必须恰好被一台服务器服务。求满足条件的最小服务器数量。

动态规划状态定义

代码中使用了三维状态数组dp来进行动态规划：

• dp[u][0]：节点u作为服务器时，以u为根的子树所需的最小服务器数量
• dp[u][1]：节点u作为客户端且被父节点服务时，子树的最小服务器数量
• dp[u][2]：节点u作为客户端且被某个子节点服务时，子树的最小服务器数量

状态转移方程

1. 当节点u是服务器时（dp[u][0]）
   此时，u的子节点可以是服务器或客户端（被u服务）：

   dp[u][0] = 1 + ∑ min(dp[v][0], dp[v][1])
   

   其中v是u的子节点。

2. 当节点u是客户端且被父节点服务时（dp[u][1]）
   此时，u的子节点必须是服务器：

   dp[u][1] = ∑ dp[v][2]
   

3. 当节点u是客户端且被某个子节点服务时（dp[u][2]）
   需要选择一个子节点作为服务器来服务u，其他子节点可以是服务器或客户端：

   dp[u][2] = min(dp[v][0] - dp[v][2]) + dp[u][1]
   

   其中v是u的子节点，dp[v][0] - dp[v][2]表示选择v作为服务器时的额外开销。

代码实现解析

1. 初始化（init函数）

   • 初始化邻接表和动态规划数组
   • dp[u][0]初始化为1（节点自身作为服务器）
   • dp[u][1]初始化为0（依赖父节点）
   • dp[u][2]初始化为无穷大（需要选择最优子节点）

2. 添加边（add_edge函数）

   • 构建树的邻接表表示

3. 深度优先搜索（dfs函数）

   • 后序遍历树，自底向上计算每个节点的状态
   • 计算三种状态的转移值

复杂度分析

• 时间复杂度：$O(N)$，每个节点仅被访问一次
• 空间复杂度：$O(N)$，主要用于存储邻接表和动态规划数组

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn=11000;
const int INF=1e6;

struct Edge
{
	int to,next;
}edge[maxn*2];

int Adj[maxn],Size;

int dp[maxn][3],n;

void init()
{
	Size=0; 
	for(int i=0;i<=n+10;i++)
	{
		Adj[i]=-1;
		dp[i][0]=1; dp[i][1]=0; dp[i][2]=INF;
	}
}

void add_edge(int u,int v)
{
	edge[Size].to=v;
	edge[Size].next=Adj[u];
	Adj[u]=Size++;
}

void dfs(int u,int fa)
{
	for(int i=Adj[u];~i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		dp[u][0]+=min(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][2];
		dp[u][2]=min(dp[u][2],dp[v][0]-dp[v][2]);
	}
	dp[u][2]+=dp[u][1];
}

int main()
{
	
	while(scanf("%d",&n)!=EOF)
	{
		if(n==-1) break;
		else if(n==0) continue;
		init();
		for(int i=0;i<n-1;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			add_edge(a,b); add_edge(b,a);
		}
		dfs(1,0);
		printf("%d\n",min(dp[1][0],dp[1][2]));
	}
	
	return 0;
}