双倍经验，双倍快乐。

题意

在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。

输出这个最小的值。

做法

Define:以下\(s\)指链或链长。

1. 证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。
2. 于是我们找到直径并记录下直径上的所有点。
3. 然后，我们枚举直径上的每一个长度小于\(s\)的最长区间（最长原因显然，因为长度越短答案肯定不会更优），并计算此时的答案，对于每一个区间的答案取min即可。
4. 考虑计算每个区间的答案。我们把直径拉出来，用两个指针\(l\)和\(r\)从左向右遍历这个直径，\(s\)即为\(l\)到\(r\)。考虑此时这个区间的答案即为\(l\)到\(r\)中每个点\(i\)的子树中最深的点的距离（我们设为\(h_i\)）（注意这里的子树是不包括直径的，即子树中所有的点都属于支链）和\(l\)到直径左端点的距离（设为\(ls\)）和\(r\)到直径右端点的距离（设为\(rt\)）的最大值。原因显然。
5. 那么我们可以预处理出\(h_i\)，并在遍历直径的时候用单调队列维护\(h\)的最大值，然后用这个值与\(ls\)和\(rt\)的最大值更新答案（取最小值）即可。

一些疑问

• 当存在多条直径时，区间似乎一定包括重心并尽量使重心居中。然而这并没有什么卵用，并且一样可以用上面的方法做，不会造成影响。

• \(s\)的左右两端一定在端点上。既是，\(s\)是可以为一个点的。

具体实现和代码

• 求直径时两次DFS即可。然后发现记录的d数组刚好可以用来当做前缀和（只是使代码略显凌乱罢了）
• 单调队列似乎要特殊记录一下链首的位置而不能用head代替，否则无法记录区间长（或者只是我没有想到更好的处理方法）
• 求深度DFS或BFS.
• 时间复杂度O(n).

（学会了一个新单词diameter，意思是直径，重音在|a|上）

#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read(){
    int x=0,w=0;char c=getchar();
    while(!isdigit(c))w|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
namespace star
{
    const int maxn=3e5+10;
    int n,l;
    int ecnt,head[maxn],nxt[maxn<<1],to[maxn<<1],dis[maxn<<1];
    inline void addedge(int a,int b,int c){
        to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;dis[ecnt]=c;
        to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;dis[ecnt]=c;
    }
    int d[maxn],mx,fa[maxn],diam[maxn],tot,sum;
    void dfs1(int x,int f,int &dia){
        fa[x]=f;
        if(mx<d[x])
            mx=d[x],dia=x;
        for(int i=head[x];i;i=nxt[i]){
            int u=to[i];
            if(u==f)continue;
            d[u]=d[x]+dis[i];
            dfs1(u,x,dia);
        }
    }
    inline void diameter(){
        int dia,dia2;
        dfs1(1,0,dia);
        mx=0;d[dia]=0;
        dfs1(dia,0,dia2);
        while(dia2!=dia){
            diam[++tot]=dia2;
            dia2=fa[dia2];
        }
        diam[++tot]=dia;
    }
    int h[maxn],dep[maxn],q[maxn],ans=0x3f3f3f3f;
    void dfs2(int x,int f){
        for(int i=head[x];i;i=nxt[i]){
            int u=to[i];
            if(u==f)continue;
            dfs2(u,x);
            dep[x]=max(dep[x],dep[u]+dis[i]);
        }
    }
    inline void solve(){
        for(int i=2;i<tot;i++){
            int x=diam[i];
            h[i]=0;dep[x]=0;
            for(int j=head[x];j;j=nxt[j]){
                int u=to[j];
                if(u==diam[i-1] or u==diam[i+1])continue;
                dfs2(u,x);
                h[i]=max(h[i],dep[u]+dis[j]);
            }
        }
        int s=1,t=0,ls=0,rt=mx,from=1;
        for(int i=1;i<=tot;i++){
            while(s<=t and d[diam[from]]-d[diam[i]]>l)from++,s+=(from>q[s]),ls=(mx-d[diam[from]]);
            while(s<=t and h[i]>h[q[t]])t--;
            q[++t]=i;rt=d[diam[i]];
            ans=min(ans,max(h[q[s]],max(ls,rt)));
        }
        printf("%d",ans);
    }
    inline void work(){
        n=read(),l=read();
        for(int a,b,c,i=1;i<n;i++)a=read(),b=read(),c=read(),addedge(a,b,c);
        diameter();
        solve();
    }
}
signed main(){
    star::work();
    return 0;
}