ECNU XCPC 2021 November Training #2

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

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

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