题意简述
给定一棵带边权无根树和一个正整数 \(s\)。在这棵树的任意直径上截取一段长度不超过 \(s\) 的路径 \(F\)，使离 \(F\) 最远的点到 \(F\) 的距离最小，求出这个距离。
思路
记 \(\delta(a, b)\) 为 \(a, b\) 之间的路径。
对于任意直径上一点 \(u\)，记 \(d'(u)\) 为 \(u\) 不经过直径上其他点所能到达的最远距离。
如图，不妨设一条直径为 \(\delta(a, b)\)，其中的一条路径 \(F = \delta(x, y)\) 满足 \(d(x, y) \le s\)。
引理： 对于直径 \(\delta(a, b)\) 上任意一点 \(u\)，总有 \(d'(u) \le d(a, u), d(b, u)\)。
证明：假设 \(d'(u) > d(a, u)\)，不妨设 \(u\) 不经过直径上其他点所能到达的最远的点是 \(a'\)（即 \(d'(u) = d(a', u)\)），则有 \(d(a', b) = d(a', u) + d(u, b) > d(a, u) + d(u, b) = d(a, b)\)，与 \(\delta(a, b)\) 是树的直径矛盾。\(d'(u) \le d(b, u)\) 同理。
由引理及 \(\operatorname{ECC}\) 的定义可得出以下性质：
-
\(z\) 对 \(\operatorname{ECC}(F)\) 的贡献是 \(d'(z)\)。
-
\(x\) 对 \(\operatorname{ECC}(F)\) 的贡献是 \(d(a, x)\)，\(y\) 对 \(\operatorname{ECC}(F)\) 的贡献是 \(d(b, y)\)。
-
\(\operatorname{ECC}(F) \le \operatorname{ECC}(\delta(x, z_2)), \operatorname{ECC}(\delta(y, z_1))\)。
证明：易得
\[\begin{cases} \operatorname{ECC}(F) = \min\{d(a, x), d'(z_1), \cdots, d'(z_2), d(b, y) \}, \\ \operatorname{ECC}(\delta(x, z_2)) = \min\{d(a, x), d'(z_1), \cdots, d(b, z_2) \}, \\ \operatorname{ECC}(\delta(y, z_1)) = \min\{d(a, z_1), \cdots, d'(z_2), d(b, y) \}. \end{cases} \]由引理知 \(d'(z_1) \le d(a, z_1), d'(z_2) \le d(b, z_2)\)，又易证 \(d(a, x) < d(a, z_1), d(b, y) < d(b, z_2)\)，代入得证。
由 1、2 我们得知对于 \(F = \delta(x, y)\) 有 \(\operatorname{ECC}(F) = \max\{d(a, x), d(b, y), \max\{d'(z)\} \}\)；由 3 我们得知仅当 \(d(x, y)\) 尽可能接近 \(s\) 时最优，这满足双指针的单调性。
使用两遍 DFS 找出一条直径，再使用一遍 DFS 求出直径上每个点的 \(d'\)。在这条直径上使用双指针枚举 \(x, y\) 确定 \(F\)；\(d(a, x)\) 和 \(d(b, y)\) 可以在尺取的过程中得出，\(\max \{ d'(z) \}\) 可以用单调队列维护，由此求得 \(\operatorname{ECC}(F)\)。 \(\min \{\operatorname{ECC}(F) \}\) 即为答案。
DFS、双指针、单调队列时间复杂度均为 \(O(n)\)，故总时间复杂度为 \(O(n)\)。
考虑进一步简化。在尺取的过程中求出所有 \(F\) 的 \(\max\{d(a, x), d(b, y) \}\) 的最小值，记为 \(r\)；求出所有 \(d'\) 的最小值，记为 \(d'(t)\)。
设 \(F' = \delta(x', y')\) 是答案对应的区间。
-
若 \(r \ge d'(t)\)，则 \(\operatorname{ECC}(F') = \max\{d(a, x'), d(b, y' )\} = r\)。
-
若 \(r < d'(t)\)，则一定有 \(t\) 在 \(F'\) 上，即 \(x' \le t \le y'\)，此时 \(\operatorname{ECC}(F') = d'(t)\)。假设 \(t\) 不在 \(F'\) 上，不妨设 \(t < x'\)，由引理知 \(d'(t) \le d(a, t) < d(a, x) \le \operatorname{ECC}(F')\)，一定不如前者优。
所以最终答案为 \(\max \{r, d'(t) \}\)。
考察存在多条直径的情况。题面已经指出直径的中点重合，可以证明每条直径不重合的两部分部分长度相等，如果 \(F'\) 包含了直径分岔的结点 \(m\)，则 \(\operatorname{ECC}(F')\) 为 \(m\) 到 \(F'\) 末端的距离。具体证明较为繁琐，这里略去。
代码
#include <iostream>
#include <vector>
struct Edge // 边
{
int to, w; // 终点和边权
};
int far; // 用于求直径端点
int fa[305], dis[305]; // fa 为父节点, dis 的用途不唯一
bool diameter[305]; // 是否在直径上
std::vector<Edge> mp[305]; // 存树
void dfs(int u, int f) // 求直径和 d'
{
fa[u] = f;
if (dis[u] > dis[far])
far = u; // 求直径的端点
for (auto i : mp[u])
if (i.to != f && !diameter[i.to]) // i.to != f 避免死循环, !diameter[i.to] 是 d' 的定义
{
dis[i.to] = dis[u] + i.w;
dfs(i.to, u);
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, s, ans = 300000;
int start, end; // 直径的端点
std::cin >> n >> s;
for (int i = 1; i < n; i++)
{
int u, v, w;
std::cin >> u >> v >> w;
mp[u].push_back({v, w});
mp[v].push_back({u, w});
}
dfs(1, 0);
start = far;
dis[start] = 0;
dfs(start, 0); // 求出直径起点后, 顺便将直径起点作为树的根
end = far;
for (int i = end, j = end; i >= 1; i = fa[i]) // 双指针, i 即 x, j 即 y, 求出 max{d(a, x), d(b, y)}
{
while (dis[j] - dis[i] > s) // 性质 3
j = fa[j];
ans = std::min(ans, std::max(dis[end] - dis[j], dis[i]));
}
for (int i = end; i >= 1; i = fa[i]) // 标记直径, 为求 d' 做准备
diameter[i] = true;
for (int i = end; i >= 1; i = fa[i]) // 求 d'
{
dis[i] = 0;
dfs(i, fa[i]);
}
for (int i = 1; i <= n; i++) // 求 d' 最大值
ans = std::max(ans, dis[i]);
std::cout << ans << "\n";
return 0;
}