题解

//本题解注释重点在双指针寻找偏心距的过程
//dfs过程请看去看模板
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> >g[100005];
int far=0,A,B,preev[100005],dis[100005],ans=(int)1e9,flag[100005];
//far储存dfs中最远的节点
//preev储存每个节点的父亲
//dis储存每个节点距离dfs开始节点的距离
//flag储存直径
void addedge(int u,int v,int w){
    g[u].push_back({v,w});
    g[v].push_back({u,w});
}

void dfs(int u,int fa){
    preev[u]=fa;                    //记录自己的fa
    if (dis[u]>dis[far])far=u;
    for (auto i:g[u]){
        int v=i.first;
        int w=i.second;
        if (v==fa || flag[v])continue;
        dis[v]=dis[u]+w;
        dfs(v,u);
    }
}

int main()
{
    int n,s;
    cin >> n >> s;
    for (int i=1;i<n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        addedge(u,v,w);
    }
    dfs(1,0);A=far; //从1开始找出最远的节点,标记为A
    dis[far]=0;dfs(far,0);B=far;//从A开始dfs,找出离A最远的B并算出每个节点距离A的距离
    swap(A,B);      //交换A,B便于理解
    for (int i=A,j=A;i;i=preev[i]){     //i从A向B遍历
        while(dis[j]-dis[i]>s){         //因为取的点越多偏心距一定不变或变小
            j=preev[j];                 //所以设置双指针,卡住刚好小于s的范围
        }
        int x=max(dis[A]-dis[j],dis[i]);//记录直径上的最大偏心距
        ans=min(ans,x);                 //记录下离两端直径最优的答案
        flag[i]=1;                      //给直径上每个点打上标记
    }
    for (int i=A;i;i=preev[i]){
        dis[i]=0;
        dfs(i,preev[i]);                //直径上以每个点为起点跑一次dfs记录每个点距离直径的距离
    }
    for (int i=1;i<=n;i++){
        ans=max(ans,dis[i]);            //取最大的偏心距
    }
    cout << ans ;                       //输出答案
    return 0;
}