gym 101667 A -Broadcast Stations【树形dp】

A 树形dp

题目大意：

一棵5e3的树，可以选择一些点，放上基站，如果u上的基站价值为d，那么距离u小于等于d的点都会被覆盖，问使得整棵树被覆盖需要的最小价值。

题目分析

设 $f\left[u\right]\left[i\right]$f[u][i] 表示从 u这个点 ，向外最多能覆盖 到距离为i的点，且他的子树都被覆盖的最小价值。

那么我们考虑 $f\left[u\right]\left[i\right]$f[u][i] 可能是在u这个点建立了一个价值为i的基站，也可能是他的子树能够覆盖到 i+1

因此 我们还需要统计 u这个点 距离他的i的子树全被覆盖所需的最小价值

定义为 g[u][i]
$g\left[u\right]\left[i\right]=\sum g\left[v\right][i-1]$g[u][i]=∑g[v][i−1]

所以我们考虑 $f\left[u\right]\left[i\right]=min\left(f\right[v\left]\right[i+1]-g[v\left]\right[i],j)+g\left[u\right][i+1]$f[u][i]=min(f[v][i+1]−g[v][i],j)+g[u][i+1]

$f\left[v\right][i+1]-g\left[v\right]\left[i\right]$f[v][i+1]−g[v][i] 表示这个v这个点最多能往外延伸到i+1的距离，（也就是删去的v的子树）
这样在树上进行dp就可以了。

考虑边界情况
我们在计算 f[u][0] 的时候， 不能直接选择 j ，因为只有 u这一个点的时候也需要消耗 1的价值，所以我们特判 f[u][0]的情况

代码详情

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3+50;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
vector<int>G[maxn];
int g[maxn][maxn];
int f[maxn][maxn]; 
int n;
void dfs(int u,int fa)
{
// cout<<u<<" fa= "<<fa<<endl;
	for(int i=0;i<G[u].size();i++) 
	{
		
		int v = G[u][i];
		if(v!=fa)
		{
			dfs(v,u);
			for(int j=1;j<=n;j++)
			{
				g[u][j] += g[v][j-1];
			}
		}
	}
	f[u][n]= n; //表示 U点 覆盖所有点需要的价值，最大是n 
	g[u][0] =n; // 初始化g[u][0] u的子树全覆盖的情况
	
	for(int i=n-1;i>=0;i--)
	{
		if(i!=0)
		f[u][i] = min(i+g[u][i+1],f[u][i+1]); //在某个位置新建一个基站 
		else if(i==0)
	  //特判=0的时候， f[u][0]表示子树都被覆盖，只覆盖u这个点的时候也需要1个 
		{
			f[u][i] = min(1+g[u][2],f[u][i+1]);
		 }
		for(int j=0;j<G[u].size();j++)
		{
			int v = G[u][j];
			if(v!=fa)
			{
				f[u][i] = min(f[u][i],f[v][i+1]-g[v][i]+g[u][i+1]);
			}
		} 
	} 
	
	g[u][0] =f[u][0];
	
	for(int i=1;i<=n;i++) g[u][i] = min(g[u][i],g[u][i-1]);
	//对于所有的子树，很显然满足这个关系。确保更新的值合理。 
	 
}
int main()
{
	scanf("%d",&n);
	memset(g,0,sizeof(g));
	memset(f,0,sizeof(f));
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
// cout<<1<<endl;
	dfs(1,0);
// cout<<2<<endl;
	printf("%d\n",g[1][0]); 
	return 0;
}