3914. 健康监测计划

单点时限: 2.0 sec

内存限制: 256 MB

QQ 小方接到了来自学校防控疫情指挥部的任务,协助指挥部部署校园内的健康监测站。

华东师范大学共有 $n$ 栋楼房,编号为 $1,2,\dots,n$,并有 $n-1$ 条双向联通的道路连接这些楼房,使得任意两栋楼房之间有且仅有一条简单路径(一条简单路径是指,从一栋大楼出发,不经过重复大楼,并在另一栋大楼结束的路径)。学校为了贯彻落实常态化疫情防控政策,决定选择一些楼房,在其中各设置一个健康监测点,实时监测路过的同学的健康状况。

虽然自动化检查仪器已经在全校普及,但是监测的过程依然不可避免地会影响学生的出入便捷性。所以学校需要精心安排监测点的位置,使得监测点数量尽可能多,而且尽量不对师生们造成太大的麻烦。具体而言,对于任意一条从某一栋楼开始在另一栋楼结束的简单路径,你需要保证路径上的监测点的数量不超过 $k$(包括起点和终点上的监测点),并在此前提下最大化监测点的数量。

输入格式

第一个输入两个整数 $n$ 和 $k$($2\le n \le 10^6$,$0 \le k \le n$),表示华师大楼房的个数以及任意一条简单路径上的监测点数目上限。

接下来 $n-1$ 行,每行输入两个不同的正整数 $u,v$($1\le u,v \le n$),表示有一条直接连接 $u$ 号楼房和 $v$ 号楼房的双向道路。

输出格式

一行,一个整数,表示最多能放置多少个健康监测站。

样例

Input
10 1
1 4
1 2
2 5
2 3
2 7
2 8
5 6
6 10
8 9
Output
1
Input
8 2
5 1
7 1
2 1
4 7
6 7
8 6
3 4
Output
4

123 人解决,176 人已尝试。

143 份提交通过,共有 866 份提交。

3.9 EMB 奖励。

创建: 1 月前.

修改: 1 月前.

最后提交: 2 天,13 小时前.

来源: N/A

题目标签