问题2431--最大权值子树(subtree)

2431: 最大权值子树(subtree)

时间限制: 2 Sec  内存限制: 256 MB
提交: 25  解决: 12
[提交] [状态] [讨论版] [命题人:]

题目描述

给定n个点的树,编号1~n,每个节点上有权值,编号为i的节点权值为2^i。BSNY想去掉k个点,并且希望剩下的点两两相互连通的,也就是剩下(n-k)个点为原先树的子树。在此基础上,BSNY想让剩下的子树权值和最大,请你编程告诉他,应该去掉哪k个点。
例如n=6, k=3,树的边为:
2 1
2 6
4 2
5 6
2 3
去掉1 3 4三个点,剩下的2 5 6三个点仍然构成树,并且权值和最大为:2^2+2^5+2^6。

输入

第一行输入n, k
接下来n-1行,输入n-1条无向边,构成树

输出

从小到大输出去掉的k个点的编号

样例输入 Copy

8 4
2 6
2 7
7 8
1 2
3 1
2 4
7 5

样例输出 Copy

1 3 4 5

提示

30%的数据 1<=k<n<=100
50%的数据1<=k<n<=1000
另有10%的数据 树退化成链
100%的数据 1<=k<n<=10^6

来源/分类