题目求最大值最小，所以考虑二分答案。假设现在我们二分出来答案是 \(mid\)，那么题目转化为：是否存在一种选点方案，选不超过 \(k\) 个点，使得所有城市通勤距离的最大值小于 \(mid\)。
首先可以发现选叶子结点是不优的：因为选父亲结点比选叶子结点的连通性贡献更大，而且对答案更优。推导一下可以发现：如果选择与叶子结点距离小于 \(mid\) 的节点，是不优的。所以可以直接将它们不选，选剩下的点。
如果剩下点的个数小于等于 \(k\)，那么答案肯定能取到 \(mid\)。如果剩下点的个数大于 \(k\)，设剩下点数有 \(x\) 个。则需要在与叶子结点距离大于等于 \(mid\) 的点中删除 \(x-k\) 个点，使得满足条件。
发现与叶子结点距离大于等于 \(mid\) 的点组成了一个联通块。这个联通块中的叶子结点（也就是度为 \(1\)）的节点不能删，因为删掉后原树的叶子结点距离就不满足了。这个联通块中度数大于 \(2\) 的点也不能删，因为删掉后联通块数量就大于 \(2\)，不符合题意。
所以只能删度数为 \(2\) 的点。不难发现删除的是一条路径，路径上每个点度数都为 \(2\)，就如下图这样。
我们记 \(w_i\) 为第 \(i\) 个节点向链外延伸的所有子树中，距离该节点最远的叶子的距离。
考虑答案怎么计算。对于每个点，我们记 \(v_i=mid-w_i\)，那么不能删除区间 \([l,r]\)，使得 \(l\le i-max(v_i,0)+1\) 并且 \(i+max(v_i,0)\le r\)。
然后使用差分维护每个点的限制区间，然后查询是否有区间满足条件即可。
时间复杂度 \(O(nlogn)\)，空间复杂度 \(O(n)\)。