题解 | #电话网络#

这题考察的是树状dp，而dp问题解题的关键是写出状态转移方程

先确定状态 :

1. f[x][0] 代表到x点时x该点不设塔，并且x点不被覆盖，x的子树都被覆盖的最小建塔数
2. f[x][1] 代表到x点是x该点设塔，由于x点设塔，那么x一定被覆盖，x的子树都被覆盖的最小建塔数
3. f[x][2] 代表到x点是x该点不设塔，且x点被覆盖，x的子树都被覆盖的最小建塔数

ok，确立完状态我们来写状态转移方程。

先看f[x][0]这个状态，由于改状态该点不设塔，且不被覆盖，那么该点的子树上的根节点也一定不设塔，否则该点x一定被覆盖 ，且子树都要被覆盖，那么子树的状态一定都是f[k][2]。假设x的子树的根节点为k 那么f[x][0]=sum{f[k][2]};

再看f[x][1]这个状态，由于该点设塔，那么对其子树的根节点是否设塔不做要求。假设x的子树的根节点为k 那么f[x][1]=sum{min{f[k][0],f[k][1],f[k][2]}}+1;

再看f[x][2]这个状态 ,由于该点不设塔，那么其子树的根节点最少有一个要设塔,那么我设一个变量w，初始值为0，如果有f[k][1]<=f[k][2]的情况，w=1。 如果w==1 f[x][2]=sum{min{f[k][1],f[k][2]}} 否则，就将f[k][1]-f[k][2]差值最小的f[k][2]变为f[k][1]. f[x][2]=sum{f[k][2]}+ min(f[k][1]-f[k][2]).

写完状态转移方程，该题已经完成了一大半，我们这时还要解决一个问题，就是该点该状态不存在的情况 假设x点下面没有子树，那么f[x][0]与f[x][2]的状态是不存在的，如果我们粗暴的将其设为0，我们就发现其根节点y，f[y][0]和f[y][2]的点都被设置为0，这显然是不对的，所以我们要对其处理。 当该点没有子节点时，f[x][0]和f[x][2]都设置为-1。 当该点的子节点中出现-1时，我们也要对其出来， 对f[x][0]而言，如果子节点有一个f[k][2]不存在，那么该点的f[x][0]状态也不存在， 对于f[x][1]而言，如果子节点有几个任意状态不存在，该状态任然存在， 对于f[x][2]而言，如果节点中有f[k][2]这个状态不存在，我们就用f[k][1]来代替它。

代码如下：

#include<vector>
#include<cstring>
using namespace std;

const int N=1e5+10;
int f[N][3];
int n;

vector<int> to [N]; //存边
int inner[N];//标记该点有无子树
const int INF=0x3f3f3f3f;
int dfs(int x,int seg,int fa)
{
	if(f[x][seg]!=-1) return  f[x][seg]; // 该点已经遍历过则不用遍历
	int ans=0;
	int mint=INF;
	if(seg==0)
	{	
	for(auto k:to[x])
	{
		if(k==fa) continue;//从父节点不能遍历
		dfs(k,2,x);
		if(f[k][2]==-1) //该子树状态不存在，那么该点的状态也不存在，直接将其赋值为-1
		{
			ans=-1;
			break;
		}
		ans+=f[k][2];
		inner[x]=1;
	}
	if(inner[x]==0) ans=-1; //如果没有子树，就赋值为-1
	}
	else if(seg==1) 
	{
		for(auto k:to[x]) //遍历每个子树
		{
			if(k==fa) continue;
			inner[x]=1;
			dfs(k,1,x);dfs(k,0,x);dfs(k,2,x);//由于该点已经确定有塔，所以子树三种情况都成立并对其去最小值
			if(f[k][0]==-1||f[k][2]==-1) 
			{
				if(!inner[k]) continue;
				else 
				{
					if(f[k][0]==-1&&f[k][2]!=-1) ans+=min(f[k][1],f[k][2]);
					else if(f[k][2]==-1&&f[k][0]!=-1) ans+=min(f[k][1],f[k][0]);
					else ans+=f[k][1];
					continue;
				}
			}
			ans+=min(f[k][1],min(f[k][0],f[k][2]));
			
		}
		ans+=1;
	}
	else 
	{	
	
		int w=0; //判断是否已经取了一颗子树使该点被覆盖
		for(auto k:to[x])
		{
			if(k==fa) continue;
			dfs(k,1,x);dfs(k,2,x);
			inner[x]=1;
			if(f[k][2]==-1) // 如果该子树中有f[k][2] 的状态不存在的情况，那么就用f[k][1]的状态代替f[k][2]
			{
				ans+=f[k][1]; 
				w=1;// 已经取了一个子树上建塔并被覆盖的状态
				continue;
			}
			if(w==0) mint=min(f[k][1]-f[k][2],mint); //如果每个子树都是f[k][1]>f[k][2]的情况，那么我就就将于f[k][1]差值最小的f[k][2]变成f[k][1]
            
				
			if(f[k][1]<f[k][2]) 
			{
				w=1;
				ans+=f[k][1];
			}
			else 
			{
				ans+=f[k][2];
			}
			
		}
		if(!w) 
		ans+=mint;//将差值最小的f[k][2]的改为f[k][1]
		if(inner[x]==0) ans=-1;
	}
	return f[x][seg]=ans;
}
void sc()
{
	cin>>n;
	memset(f,-1,sizeof f);

	memset(inner,0,sizeof inner);

	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		
		to[v].push_back(u);
		to[u].push_back(v);//建立树边
	}
	dfs(1,0,0);dfs(1,1,0);dfs(1,2,0);
	cout<<min(f[1][1],f[1][2])<<"\n";//在根节点我一定取根节点被覆盖的情况
// 	for(int i=1;i<=n;i++)
// 	{
// 		cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl;
// 	}
}
int main()
{

	 sc();
}