题解 P1272 【重建道路】

查看原题请戳这里

状态设计

一开始我设计$f[i][j]$表示在以$i$为根节点的子树上保留$j$个节点需要断掉的最少的边数，但是这样设计状态虽然思考起来比较直观，但是状态转移貌似比较麻烦，所以我们直接用$f[i][j]$表示在以$i$为根的子树上删去$j$个节点需要去掉的最少的边数，$ans=\min(f[u][siz[u]-p]+f[u][siz[u]])$，其中$siz[u]-p$是我们要在这颗以$u$为根节点的子树上删去的点数，$f[u][siz[u]]$是把以$u$为根节点的子树和这颗树的剩余部分分开需要删去的边数。

若$u$为非根节点，则$f[u][siz[u]]=1$（把$u$和$father[u]$之间的边删去）；若$u$为根节点，则$f[u][siz[u]]=0$（根节点没有父亲节点，不用删）。

状态转移

状态转移和分组背包相似，用到了泛化物品的思想。

我们遍历这颗树，这个过程相当于在枚举组别（以同一个节点$u$为根的$f[u][1-siz[u]]$这些状态当成物品分到一组）。

f[u][j] = min(f[u][j],f[u][j - k] + f[v][k]);

这就是状态转移方程，尝试在当前这颗子树中选择一些节点尝试能不能得到更优的状态。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 100000000000
#define re register
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define qwq printf("qwq\n");
#define int long long

using namespace std;

long long read()
{
	register long long x = 0,f = 1;register char ch;
	ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
	while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
	return x * f;
}

int n,p,cnt,ans,x,y,z,d[1000005],f[155][155],siz[1005];

struct edge{
	int to,nex,w;
}e[2000005];

void add(int x,int y)
{
	e[++cnt].to = y;
	e[cnt].nex = d[x];
	d[x] = cnt;
}

void dfs1(int u,int fa)
{
	siz[u] ++;
	for(int i = d[u]; i; i = e[i].nex)
	{
		int v = e[i].to;
		if(v == fa) continue;
		dfs1(v,u);
		siz[u] += siz[v];
	}
	f[u][0] = 0;
	f[u][siz[u]] = 1;
}

void dfs2(int u,int fa)
{
	for(int i = d[u]; i; i = e[i].nex)
	{
		int v = e[i].to;
		if(v == fa) continue;
		dfs2(v,u);
		for(int j = siz[u] - 1; j; j--)
			for(int k = 0; k <= j; k++)
				f[u][j] = min(f[u][j],f[u][j - k] + f[v][k]);
	}
	if(siz[u] >= p) ans = min(ans,f[u][siz[u] - p] + f[u][siz[u]]);
}

signed main()
{
	n = read(); p = read();
	ans = INF;
	for(int i = 1; i < n; i++)
	{
		x = read(); y = read();
		add(x,y); add(y,x);
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			f[i][j] = INF;
	dfs1(1,1);
	f[1][siz[1]] = 0;
	dfs2(1,1);
	printf("%lld\n",ans);
    return 0;
}