一种简单的打法
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=510000,inf=0x3f3f3f3f;
struct edge{int x,y,c,pre;}a[N*2];int alen,last[N];
inline void ins(int x,int y,int c){a[++alen]={x,y,c,last[x]};last[x]=alen;}
int res,num;
int dt[N],t,sum[N];
int d[N],f[N],rd[N];bool v[N];
void dfs(int x,int fa){
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(y==fa||v[y])continue;
f[y]=x;rd[y]=k;d[y]=d[x]+a[k].c;
if(res<d[y])res=d[y],num=y;
dfs(y,x);
}
}
int main(){
int n,s;scanf("%d%d",&n,&s);
for(int i=1;i<n;++i){
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
res=-inf;d[1]=0;dfs(1,-1);int p=num;
res=-inf;d[p]=0;dfs(p,-1);int q=num;
while(p!=q){
v[q]=1;dt[++t]=q;
sum[t+1]=sum[t]+a[rd[q]].c;
q=f[q];
}dt[++t]=q;v[q]=1;sum[t+1]=sum[t]+a[rd[q]].c;
int maxd=-inf;
for(int i=1;i<=t;++i){
res=-inf;d[dt[i]]=0;dfs(dt[i],-1);
maxd=max(maxd,res);
}
int ans=inf;
for(int i=1,j=1;i<=t;++i){
while(j<t&&sum[j+1]-sum[i]<=s)++j;
ans=min(ans,max(maxd,max(sum[i],sum[t]-sum[j])));
}
printf("%d\n",ans);
return 0;
}
%%%
NB