解题思路

问题要求在最多修改 $k$ 个基站频率的前提下，使相邻基站频率差的最大值（干扰度）尽可能小。由于可以任意设置修改后的频率值，当我们将目标干扰度限制为某个阈值 $L$ 时，若一条边两端基站的初始频率差 $|f_u-f_v|>L$，则该边会“破坏”我们的目标，必须修改这条边至少一个端点的频率；反之，若 $|f_u-f_v|\le L$，则即使两端点都不修改，该边也能满足要求。

将初始频率差大于 $L$ 的边称为 坏边。问题转化为：在坏边构成的边集上，是否存在一个顶点覆盖（选出的顶点集与每条坏边相邻），且顶点覆盖的大小不超过 $k$？树上最小顶点覆盖可以通过树形 DP 在 $O(n)$ 时间内求出。再对 $L$ 进行二分查找即可得到最小的可行干扰度。

具体步骤：

1. 计算每条树边的权值 $w_e=|f_u-f_v|$，并记录最大权值 $W=\max w_e$。