洛谷 P1272 重建道路

题目链接

题解

树形dp

\(f_{i, j}\)表示以\(i\)为根的子树切出联通块大小为\(j\)的最小答案

显然\(f[i][1]\)为与\(i\)连的边数

设\(v\)是\(u\)的儿子

那么有\(f[u][i]=f[u][i-j]+f[v][j]-2\)，因为\(u->v\)这条边算了两次

• 注意\(i\)要从大到小枚举

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

inline int gi() {

    int f = 1, s = 0;

    char c = getchar();

    while (c != '-' && (c < '0' || c > '9')) c = getchar();

    if (c == '-') f = -1, c = getchar();

    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();

    return f == 1 ? s : -s;

}

int n, p;

const int N = 200;

int f[N][N];

struct node {

	int to, next;

}g[N<<1];

int last[N], gl, siz[N];

inline void add(int x, int y) {

	g[++gl] = (node) {y, last[x]};

	last[x] = gl;

	return ;

}

#define Min(a, b) (a>b?b:a)

inline void dfs(int u, int fa) {

	siz[u] = 1;

	f[u][1] = 0;

	for (int i = last[u]; i; i = g[i].next) {

		int v = g[i].to;

		f[u][1]++;

		if (v == fa) continue;

		dfs(v, u);

		siz[u] += siz[v];

	}

	for (int i = last[u]; i; i = g[i].next) {

		int v = g[i].to;

		if (v == fa) continue;

		for (register int j = siz[u]; j > 1; j--)

			for (register int k = 1; k < j; k++)

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

	}

	return ;

}

int main() {

	n = gi(), p = gi();

	for (int i = 1; i < n; i++) {

		int u = gi(), v = gi();

		add(u, v); add(v, u);

	}

	memset(f, 0x3f, sizeof(f));

	dfs(1, 0);

	int ans = f[1][p];

	for (int i = 2; i <= n; i++)

		ans = Min(ans, f[i][p]);

	printf("%d\n", ans);

    return 0;

}