算法

(二分,树的直径,贪心,树的遍历) $O(NlogS)$

题目中说所有直径的中点均重合。
偏心距也有类似的性质：不管从哪条直径来求最小偏心距，答案都是唯一的。

因此我们可以先找出任意一条直径，这里可以用两次找最长路的方式：

1. 任选一点作为起点，找出距离起点的最远点 u；
2. 再找出距离 u 最远的点 v，则 u和v之间的路径就是树的一条直径。

然后枚举最小偏心距，判断在直径上是否存在一段长度不超过 $s$ 的路径，使得其余所有点到路径的距离小于等于枚举的值。
如果偏心距等于 $d$ 是满足的，那么当偏心距大于 $d$ 时也一定可以满足，因此我们可以通过二分来枚举。

接下来在直径上找到与 u 的距离不超过 mid 的前提下，距离u最远的节点，作为节点 p。类似地，在直径上找到与 v 的距离不超过 mid 的前提下，距离 v 最远的节点，作为节点 q。

根据直径的最长性，任何从 u, p 之间分叉离开直径的子树，其最远点与 p 的距离都不会比 u 更远。所以 p, q就是在满足直径两侧的那部分节点偏心距不超过 mid 的前提下，尽量靠近树网中心的节点。

接下来判断 p, q 之间的距离是否不超过 s，以及p, q之间的所有点到其他所有点的最短距离是否不超过mid即可。

时间复杂度

假设所有边长的总和是 $S$，树中节点数是 $N$，则我们一共会二分 $logS$ 次，每次判断需要 $O(N)$ 的时间，因此总时间复杂度是 $O(NlogS)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 500010, M = N * 2;

int n, s;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N], pre[N];
vector<PII> path;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int start)
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
    dist[start] = 0;
    q[0] = start;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                pre[j] = t;
                dist[j] = dist[t] + w[i];
                q[ ++ tt] = j;
            }
        }
    }
}

int bfs_max_dist(int start)
{
    int res = 0;
    int hh = 0, tt = 0;
    q[0] = start;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        res = max(res, dist[t]);

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = true;
                dist[j] = dist[t] + w[i];
                q[ ++ tt] = j;
            }
        }
    }
    return res;
}

int get_max()
{
    int t = 1;
    for (int i = 1; i <= n; i ++ )
        if (dist[t] < dist[i])
            t = i;
    return t;
}

bool check(int mid)
{
    int u = 0, v = path.size() - 1;
    while (u + 1 < path.size() && path[u + 1].second <= mid) u ++ ;
    while (v - 1 >= 0 && path.back().second - path[v - 1].second <= mid) v -- ;
    if (u > v) return true;
    if (path[v].second - path[u].second > s) return false;

    memset(st, false, sizeof st);
    memset(dist, 0, sizeof dist);
    for (auto p : path) st[p.first] = true;

    for (int i = u; i <= v; i ++ )
        if (bfs_max_dist(path[i].first) > mid)
            return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &s);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d",  &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    bfs(1);
    int u = get_max();
    bfs(u);
    int v = get_max();
    while (v != -1)
    {
        path.push_back({v, dist[v]});
        v = pre[v];
    }
    reverse(path.begin(), path.end());

    int l = 0, r = 2e9;
    while (l < r)
    {
        int mid = (LL)l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}