algorithm - 卡在图算法任务上

Question

我目前正在尝试解决去年波兰大学锦标赛的算法问题，内容如下:

The Lord Mayor of Bytetown plans to locate a number of radar speed cameras in the city. There are n intersections in Bytetown numbered from 1 to n, and n-1 two way street segments. Each of these street segments stretches between two intersections. The street network allows getting from each intersection to any other.

The speed cameras are to be located at the intersections (maximum one per intersection), wherein The Lord Mayor wants to maximise the number of speed cameras. However, in order not to aggravate Byteland motorists too much, he decided that on every route running across Bytetown roads that does not pass through any intersection twice there can be maximum k speed cameras (including those on endpoints of the route). Your task is to write a program which will determine where the speed cameras should be located.

Input

The first line of input contains two integers n and k (1 <= n, k <= 1000000): the number of intersections in Bytetown and maximum number of speed cameras which can be set up on an individual route. The lines that follow describe Bytetown street network: the i-th line contains two integers a_i and b_i (1 <= a_i, b_i <= n), meaning that there is a two-way street segment which joins two intersections numbered a_i and b_i.

Output

The first output line should produce m: the number describing the maximum number of speed cameras, that can be set up in Byteland. The second line should produce a sequence of m numbers describing the intersections where the speed cameras should be constructed. Should there be many solutions, your program may output any one of them. Example

For the following input data:

5 2
1 3
2 3
3 4
4 5

one of the correct results is:

3
1 2 4

所以从有多少团队解决了这个问题来看，我猜它不会太难，但我仍然几乎立即陷入困境，不知道如何继续前进。因为我们知道“在每条穿过 Bytetown 道路且不经过任何十字路口两次的路线上，可以有最大 k 速度的摄像头”，我想我们首先必须以某种方式将图表分解成组件，成为城镇周围的可能路线。仅此一项似乎是一件非常困难的事情，因为假设有一个十字路口有 4 条高速公路，它已经为每个入口点创建了三个可能的方向，从而形成了 12 条路线。更不用说当有更多这样的四手交叉时情况会变得多么复杂。

也许我从错误的角度处理任务？你能帮忙吗？

Answer 1

这里似乎贪心起作用

while k >= 2  
    mark all leaves of the tree and remove them
    k = k - 2;

if ( k == 1 ) 
   mark any 1 of remaining vertices