题意

给一颗树，求一条长度不超过 $s$ 的简单路径，使得树上所有点到路径的距离的最大值最小。

题解

首先根据直径的最长性，将这条路径选在直径上显然比选在其他地方优。

容易得到一个 $O(n^2)$ 的暴力，直接枚举直径的一段，另一段一定是直径上距离它最远的一个点。

考虑对其优化。

设直径为 $x$ 到 $y$ 的路径，当前选择了 $a$ 到 $b$ 的路径，$d_i$ 表示 $i$ 不经过直径可以到达最远的点到 $i$ 的距离，当前答案就是：

可以直接单调队列 $O(n)$。

但有更简单的做法，直接变成

最后面的是个定值，直接求，前面的双指针扫一遍就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,s,dep[N],max1,max2,maxdep[N],rt,leaf,f[N],anss=1e9,ans;
bool vis[N];
vector<pair<int,int> > e[N];
void get(int x,int fa,int D){
    if(D>max1)max2=x,max1=D;
    for(auto i:e[x]){
        int y=i.first;
        if(y==fa)continue;
        get(y,x,D+i.second);
    }
}
void dfs(int x,int fa){
    f[x]=fa;
    for(auto i:e[x]){
        int y=i.first,z=i.second;
        if(y==fa)continue;
        dep[y]=dep[x]+z;
        dfs(y,x);
    }
}
void work(int x,int fa){
    maxdep[x]=dep[x];
    for(auto i:e[x]){
        int y=i.first,z=i.second;
        if(y==fa)continue;
        work(y,x);
        if(!vis[y])maxdep[x]=max(maxdep[x],maxdep[y]);
    }
    if(vis[x])ans=max(ans,maxdep[x]-dep[x]);
}
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].emplace_back(y,z);
        e[y].emplace_back(x,z);
    }
    get(1,0,0);
    rt=max2;
    max1=max2=0;
    get(rt,0,0);
    leaf=max2;
    dfs(rt,0);
    int now=leaf;
    for(;now!=rt;now=f[now])vis[now]=1;
    vis[rt]=1;
    work(rt,0);
    int R=dep[leaf],L=0,l=leaf,r=leaf;
    for(;l!=rt;l=f[l]){
        while(r!=rt&&dep[l]-dep[f[r]]<=s)R=R-dep[r]+dep[f[r]],r=f[r];
        anss=min(anss,max(ans,max(L,R)));
        L=L-dep[f[l]]+dep[l];
    }
    printf("%d",anss);
}