P1272 重建道路

题目传送门

算法:树型DP

定义\(dp[i][j]\) 表示在节点 i ，获得大小为 j 的子树所需要删除的边的个数。

那我们先\(dfs\)一遍，把每棵子树的节点数求出来，那么\(dp[i][1]\)就是\(i\)的儿子数

转移方程为:
\(dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-1)\)

为什么要减一呢？因为没有考虑v和i节点之间相连的那一条边，很显然是不可以拆掉的，所以拆掉的边数必须要减去1

#include <bits/stdc++.h>
using namespace std;
int n,p,indug[209],dp[209][209];
struct p{
	int to,nxt;
}d[209];int head[209],cnt=1,size[209];
void add(int u,int v){
	d[cnt].to=v,d[cnt].nxt=head[u],head[u]=cnt++;
}
void SIZE(int now)
{
	size[now]++;
	for(int i=head[now];i;i=d[i].nxt)
	{
		int v=d[i].to;
		SIZE(v);
		size[now]+=size[v];
	}
}
//dp[i][j]在以i为根的子树中保留j棵的最小代价 
void dfs(int now)
{
	int sumn=1; 
	dp[now][size[now]]=0;
	for(int i=head[now];i;i=d[i].nxt)
	{
		int v=d[i].to;
		dfs(v);sumn+=size[v];//sumn记录有几个孩子(包括自己) 
		for(int j=sumn;j>=1;j--)//最多可以砍掉sumn次
			for(int k=1;k<j;k++)
				dp[now][j]=min(dp[now][j],dp[now][j-k]+dp[v][k]-1);
				//少砍了k次，就要在子树中砍回来	 
	}
} 
int main()
{
	cin>>n>>p;
	memset(dp,20,sizeof(dp));
	for(int i=1;i<=n;i++)	dp[i][1]=0;
	for(int i=1;i<n;i++)
	{
		int l,r;
		cin>>l>>r;
		add(l,r);
		indug[r]++;dp[l][1]++;//记录l有几个儿子 
		//因为以l为根的子树保留1个节点肯定砍掉所有儿子 
	}
	int root;
	for(int i=1;i<=n;i++)
	if(indug[i]==0)	root=i;
	SIZE(root);
	dfs(root);
	int ans=dp[root][p];
	for(int i=1;i<=n;i++)
	ans=min(ans,dp[i][p]+1);//保留子树的话，要多砍与父节点连的那条边
	cout<<ans;
	return 0; 
}

P1272 重建道路

原文：https://www.cnblogs.com/iss-ue/p/12580931.html