4287532_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

#define inf 0xfffff

using namespace std;

int n, p;
vector <int> map[150];
int best[150][151];

void dfs(int u, int fa)
{
	int i, j, k;

	if (map[u].size() == 1)
	{
		best[u][1] = 1;
		for (i = 2; i <= p; i++)
			best[u][p] = inf;
		return ;
	}
	for (i = 0; i < map[u].size(); i++)
	{
		int v = map[u][i];
		if (v == fa)
			continue;
		dfs(v, u);
	}
	best[u][1] = map[u].size();
	for (i = 2; i <= p; i++)
	{
		best[u][i] = inf;
		for (k = 0; k < map[u].size(); k++)
		{
			if (map[u][k] == fa)
				continue;
			for (j = 1; j < i; j++)
			{
				int tmp = best[u][j] + best[map[u][k]][i - j] - 1;
				if (tmp < best[u][i])
					best[u][i] = tmp;
			}
		}
	}
}

int main()
{
	int a, b;
	int i;

	scanf("%d%d", &n, &p);
	for (i = 1; i < n; i++)
	{
		scanf("%d%d", &a, &b);
		a--;b--;
		map[a].push_back(b);
		map[b].push_back(a);
	}
	dfs(0, -1);
	int ans = best[0][p];
	for (i = 1; i < n; i++)
	{
		if (best[i][p] + 1 < ans)
			ans = best[i][p] + 1;
	}
	printf("%d\n", ans);
	return 0;
}