记录编号	194352	评测结果	AAAAAAAAAA
题目名称	781.[SOJ 1140] 国王的遗产	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2015-10-16 15:25:40	内存使用	1.12 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, k, ans, pos, root = 1, left_minp = 1, sum, siz[30005], minp[30005];
int h[30005], nx[60005], to[60005];
bool vis[30005];
 
void dfs(int u, int fa)
{
	siz[u] = 1;
	minp[u] = u;
	for(int i = h[u]; i; i = nx[i])
	{
		if(to[i] == fa || vis[to[i]]) continue;
		dfs(to[i], u);
		siz[u] += siz[to[i]];
		minp[u] = min(minp[u], minp[to[i]]);
	}
	if(min(sum-siz[u], siz[u]) >= ans)
	{
		ans = min(sum-siz[u], siz[u]);
		if(sum-siz[u] > siz[u]) root = fa, pos = u;
		if(sum-siz[u] < siz[u]) root = u, pos = fa;
		if(sum-siz[u] == siz[u])
		{
			if(minp[u] == left_minp) root = fa, pos = u; 
			else root = u, pos = fa;
		}
	}
}
 
int main()
{
	freopen("legacy.in", "r", stdin);
	freopen("legacy.out", "w", stdout);
	
	scanf("%d %d", &n, &k);
	for(int i = 1; i < n; i++)
	{
		int a, b; scanf("%d %d", &a, &b);
		nx[i*2-1] = h[a]; h[a] = i*2-1; to[i*2-1] = b;
		nx[i*2] = h[b]; h[b] = i*2; to[i*2] = a;
	}
	
	sum = n;
	for(int i = 1; i < k; i++)
	{
		memset(siz, 0, sizeof siz);
		memset(minp, 0x3f, sizeof minp);
		ans = 0;
		dfs(root, 0);
		vis[pos] = 1;
		while(vis[left_minp] && left_minp <= n) left_minp++;
		sum -= ans;
		printf("%d ", ans);
	}
	printf("%d", sum);
	return 0;
}