思路

树的直径有如下性质：对于树上的任意节点 $x$，满足距离 $x$，最远的点位于直径的两端点之一。

令直径上的点为 $u_{1..t}$，$d_x$ 表示不经过直径能达到的最远的距离。

为了使偏心距更小，显然核的两端点距离在不超过 s 的情况下越长越好，所以可以得出，核在直径上。

可以枚举在直径上（$u_1$ 到 $u_t$）的核的两端点 $u_i$ 和 $u_j$（$i < j$，$dist(i, j) \le s$），对于这一个核，偏心距就是 $max(\max_{i \le k \le j}{d_{u_k}}, dist(u_1, u_j), dist(u_i, u_t))$。

因为只需要求 距离 $d_{u_1}$ 和 $d_{u_t}$ 的距离，所以可以使用前缀/后缀和，记录直径上每一个点距离两段的距离。

又因为 $\forall k1 \in [1, i], d_{u_{k1}} \le dist(u_1, u_j)$，$\forall k2 \in [j, t], d_{u_{k2}} \le dist(u_i, u_t)$，所以可以直接将 $k$ 的范围调整为 $1 \le k \le t$，这样用双指针就可以做了。

复杂度：$O(N)$。

代码

#include <bits/stdc++.h>
#define PII pair <int, int>
#define LL long long
#define x first
#define y second

using namespace std;

const int N = 500010;
int n, s;
bool vis[N];
vector <PII> v[N];

// 求出树上各点距离指定节点的距离并维护最远点
int d[N], fa[N], p;
void dfs(int x)
{
    if(d[x] > d[p])
        p = x;
    for(PII to : v[x])
    {
        if(to.x == fa[x] || vis[to.x]) continue;

        d[to.x] = d[x] + to.y;
        fa[to.x] = x;
        dfs(to.x);
    }
}

vector <int> path;
int lst[N], nxt[N];
int query_mx()
{  
    // 处理前后缀和
    for(int i = p; i; i = fa[i])
    {
        path.push_back(i);
        nxt[i] = d[i];
        lst[i] = d[p] - nxt[i];
        vis[i] = 1;
    }

    // 计算 d[u[i]] 和 max(d[u[k]])
    int mx = 0;
    for(int i : path)
    {
        d[i] = 0;
        dfs(i);
        mx = max(mx, d[p]);
    }

    return mx;
}

int work()
{
    dfs(1);
    d[p] = fa[p] = 0;
    dfs(p);

    int ans = 2e9, mx = query_mx();
    // 双指针
    for(int i = 0, j = 0; i < path.size(); i ++ )
    {
        int idi = path[i];
        // 核越长越好
        while(j + 1 < path.size() && lst[path[j + 1]] - lst[idi] <= s)
            j ++ ;
        // 计算最小偏心距
        ans = min(ans, max({mx, lst[idi], nxt[path[j]]}));
    }

    return ans;
}

signed main()
{  
    scanf("%d%d", &n, &s);
    for(int i = 1, x, y, z; i < n; i ++ )
    {
        scanf("%d%d%d", &x, &y, &z);
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

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

    return 0;
}