[题解]1037道路重建

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 1 分钟

题目描述

problem.png

题解

记$dp[i][j]$表示在以$i$为根的子树中保留$j$个牛棚需要摧毁的最小道路数，显然$dp[i][1]$等于与$i$相连的道路数。

对于所有的$v \in son_{i}$,我们可以枚举在$v$的子树中保留的牛棚树进行转移。方程:

$dp_{k,j} = min(dp[k][j - l] + dp[v][l] - 2)$ $(1<=j<=p,1<=l<j)$

注意转移中的$-2$,这是由于在$dp[k][j-l]和dp[v][l]$中，$k与v$的连边都被计算了一次，实际上这条边需要保留

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , p;
int Size[160] , Son[160][160] , tot[160];
int dp[160][160];

int dfs(int k)
{
	tot[k] = 1;
	for(int i = 1; i <= Size[k]; i ++)
	{
		tot[k] += dfs(Son[k][i]);
	}
	return tot[k];
}

void Dfs(int k , int fa)
{
	if(Son[k][1] == 0) 
	{
		return;
	}
	for(int i = 1; i <= Size[k]; i ++)
	{
		int v = Son[k][i];
		if(v == fa) continue;
		Dfs(v , k);
		for(int j = p; j >= 1; j --)
		{
			for(int l = 1; l < j; l ++)
			{
				dp[k][j] = min(dp[k][j] , dp[k][j - l] + dp[v][l] - 2);
			}
		}
	}
}   

int main()
{
	n = read() , p = read();
	for(int i = 1; i < n; i ++)
	{
		int u = read() , v = read();
		Son[u][++ Size[u]] = v;
		Son[v][++ Size[v]] = u;
	}
	memset(dp , 0x3f , sizeof(dp));
	for(int i = 1; i <= n; i ++) dp[i][1] = Size[i];
	Dfs(1 , 0);
	int ans = INT_MAX;
	for(int i = 1; i <= n; i ++) ans = min(ans , dp[i][p]);
	printf("%d\n" , ans);
	return 0;
}