题目描述

Panel 国每年举办名为 Number Games的节目,全国每个区都将派出一名代表参赛。

该国有n个区,编号从1到n,每个区只有一条路径连接到其他区。每个区有一定数量的粉丝,来自$i$区的选手的粉丝数等于$2^i$。

今年,总统决定降低成本。他想从比赛中取消$k$个参赛者。然而,被取消比赛资格区域的民众因此将很愤怒,他们将不允许任何人穿过他们的区域。

总统希望确保所有剩下的参赛者都来自可以相互联系的地区。他还希望最大化参赛选手的粉丝总数。

总统应该删除哪些参赛者?

输入格式

输入的第一行包含两个整数 $n$ and $k$ ($1 leq k < n leq 10^6$) — Panel 国的区域总数,以及总统希望取消的参赛者个数。 接下来 $n-1$ 行每行包含两个整数 $a$ 和 $b$ ($1 leq a, b leq n$, $a e b$), 描述连接两个不同区域 $a$ 和 $b$ 的双向道路。保证每两个区域间至多有一条路。

输出格式

输出 $k$ 个由空格分隔开的整数: 以升序排列的所有应该被移除的区域编号。

样例
输入
6 3
2 1
2 6
4 2
5 6
2 3

输出
1 3 4

思路

我们发现点权是$2^i$,也就是说最大的点权比剩下的加起来都大。

所以我们要尽量保留编号大的点,直接贪心就可以了。

具体地,以$n$为根预处理倍增数组,直接保留点$n$,然后从大到小$O(n)$枚举每一个点,倍增找出它离保留的点的最近距离,暴力标记路径上的所有点。

代码

  1. xgzepto
    Jul 13, 2018

    markdown
    测试

    Reply