题解

思路

只考虑所有标记点构成的集合。设其中距离最远的两个点为 $A,B$，距离为 $D$。任意顶点到全部标记点的最大距离至少为 $\lceil D/2\rceil$；而直径路径的中点到每个标记点的距离都不超过该值。因此答案为 $\lceil D/2\rceil$。

做法

小规模枚举每个候选顶点，遍历树求它到标记点的最远距离。

若只有一个标记点，选择它自身，答案为 0。

一般情况从任一标记点遍历，取最远标记点 $A$；再从 $A$ 遍历，取最远标记点距离 $D$。输出 $(D+1)/2$。

正确性证明

对任意顶点 $v$，由三角不等式 $d(A,B)\le d(A,v)+d(v,B)$，故两者至少一个不小于 $\lceil D/2\rceil$。另一方面，标记点集合的直径路径中点到任意标记点的距离不超过 $\lceil D/2\rceil$，否则该标记点与 $A$ 或 $B$ 会形成更长距离，矛盾。上下界相等，公式成立。两次遍历准确找到树上给定点集的一对直径端点。

复杂度分析

每组进行两次树遍历，时间复杂度 $O(n)$，空间复杂度 $O(n)$。