O($n$ 树的直径)

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

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

任选一点作为起点，找出距离起点的最远点 $u$；

再找出距离 $u$ 最远的点 $v$，则 $u$和$v$之间的路径就是树的一条直径。

然后枚举直径上的距离小于等于$m$的一段，找到左边，右边和往下的最小值.

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=500010,M=N*2,INF=0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int fa[N],dist[N];
int q[N],sum[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u,int father) //找到从u开始走到的最远的点
{
    int res=u;
    fa[u]=father;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==father||st[j]) continue; //如果是父亲节点或者是直径上的点就不用继续了
        dist[j]=dist[u]+w[i];
        int k=dfs(j,u);
        if(dist[k]>dist[res]) 
        {
            res=k;
        }
    }
    return res;
}
int work()
{
    int u=dfs(1,-1);
    dist[u]=0; //找到从u开始走到的最远的点
    int v=dfs(u,-1);
    int cnt=0;
    for(int i=v;i!=-1;i=fa[i]) //标记直径上的所有点
    {
        q[cnt++]=i;
        st[i]=true;
        if(fa[i]!=-1)
        {
            sum[cnt]=sum[cnt-1]+dist[i]-dist[fa[i]];
        }
    }
    int t1=0; //直径上的点往下的最大值
    for(int i=0;i<cnt;i++)
    {
        int j=q[i];
        dist[j]=0;
        int k=dfs(j,-1);
        t1=max(t1,dist[k]);
    }
    int res=INF;
    for(int i=0,j=0;i<cnt;i++)
    {
        while(sum[i]-sum[j]>m) j++; //超过长度了
        int t2=sum[j]-sum[0]; //最下方
        int t3=sum[cnt-1]-sum[i]; //最右方
        int d=max({t1,t2,t3});
        res=min(res,d); //更新最小值
    }
    return res;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++) //获取树
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cout<<work();
    return 0;
}