更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19359545

大意

求一颗树上，分离出来 $p$ 个点，使得其所需减少的边最小，求这个值。

思路

考虑树上背包。

定义状态 $f_{u, j}$ 表示 $u$ 节点，切掉 $j$ 个所需的最小花费。

那么我们的初始状态就是 $f_{u, 0} = 0$, $f_{u, sz_u} = 1$。

然后我们考虑如何进行转移：

$f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{v, k})$

然后考虑我们的答案如何进行计算，显然是 $f_{u, sz_u - p} + f_{u, sz_u}$，这个地方的 $f_{u, sz_u}$ 的值显然是 $1$，但是只有根节点是 $0$。

这个地方实际上就是为了让你的选出来的这 $p$ 个点与你原来的 $u$ 子树脱离，显然需要你删一条父边。

代码

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

const int MAXN = 155;

struct node{
	int to, nxt;
}e[MAXN];
int sz[MAXN], n, p;
int h[MAXN], tot = 0;
void add(int x, int y){
	e[++ tot] = {y, h[x]};
	h[x] = tot;
}

int f[MAXN][MAXN];

void dfsz(int u, int fa){
	sz[u] = 1;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfsz(v, u);
		sz[u] += sz[v];
	}
	f[u][0] = 0;
	f[u][sz[u]] = 1;
}

int ans = 1e9;

void dfs(int u, int fa){
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v, u);
		for(int j = sz[u] - 1;j >= 0;j --){
			for(int k = 0;k <= j;k ++){
				f[u][j] = min(f[u][j], f[u][j - k] + f[v][k]);
			}
		}
	}
	if(sz[u] - p >= 0){
        if(u == 1) ans = min(ans, f[u][sz[u] - p]);
        else ans = min(ans, f[u][sz[u] - p] + 1);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> p;

	for(int i = 1;i < n;i ++){
		int u, v; cin >> u >> v;
		add(u, v); add(v, u);
	}
	memset(f, 0x3f3f3f, sizeof(f));
	dfsz(1, 0);
	dfs(1, 0);
	cout << ans << '\n';
	return 0;
}

定义 $f(u,k)$ 表示以 $u$ 为根的子树里有 $k$ 个节点与 $u$ 联通的最小道路，$size(u)$ 为 $u$ 的子树内节点个数。

初始状态：$\forall u \in [1,n],f(u,1)=|son_u|$，其中 $|son_u|$ 表示 $u$ 的出边个数。

转移方程：

$$\sum\limits_{v\in son_u,j\in [1,size(u)],k\in [1,size(v)]} f(u,j+k)=\min\{f(u,j)+f(v,k)-2\}$$

其中 $-2$ 是因为最初 $u,v$ 两点的连边被断开，多加的 $2$ 要在这里减回来。

感性理解一下为什么说时间复杂度是 $\Theta(n^2)$ 的：

发现主要的时间复杂度是在 $j,k$ 的枚举上，而 $j,k$ 的枚举其实等价于枚举点对。

原因不难理解，每两个节点只有在它们的 LCA 处会被枚举到。

因此，总的时间复杂度是 $\Theta(n^2)$