D49 树的直径 P2491 [SDOI2011] 消防

// 两次DFS+双指针 O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=300010;
int n,s,p,l,d[N],pre[N],col[N];
vector<pair<int,int>> e[N];

void dfs(int u,int fa){
  if(d[u]>d[p]) p=u; //记录最远点
  pre[u]=fa; //记录路径
  for(auto [v,w]:e[u]){
    if(v==fa||col[v]) continue;
    d[v]=d[u]+w;
    dfs(v,u);
  }
}
int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>n>>s;
  for(int i=1,x,y,z;i<n;i++){
    cin>>x>>y>>z;
    e[x].emplace_back(y,z);
    e[y].emplace_back(x,z);
  }
  dfs(1,0); d[p]=0;
  dfs(p,0); l=p;
  
  int ans=2e9;
  for(int i=l,j=l;i;i=pre[i]){ //直径上的答案
    while(d[j]-d[i]>s) j=pre[j];
    ans=min(ans,max(d[i],d[l]-d[j]));
  }
  
  for(int i=l;i;i=pre[i])col[i]=1; //直径染色
  for(int i=l;i;i=pre[i]){ //直径外的答案
    p=i; d[p]=0;
    dfs(i,pre[i]);
    ans=max(ans,d[p]);
  }
  printf("%d\n",ans);
}