noip版：洛谷1099
加强版：bzoj1999
双倍经验（与bzoj1999相同）：bzoj2282
对于n<=300的，跑一遍floyd，枚举所有在直径上的线段即可
#include<bits/stdc++.h>
using namespace std;
int n,s,x,y,z,dis[303][303],mx,a[303],b[303],cnt,i,j,k,l,p,ans;
int main(){
scanf("%d%d",&n,&s);
memset(dis,63,sizeof(dis));
for (i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z),dis[x][y]=dis[y][x]=z,dis[i][i]=0;
dis[n][n]=0;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (dis[i][j]<1e9) mx=max(mx,dis[i][j]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (dis[i][j]==mx) a[++cnt]=i,b[cnt]=j;
ans=1e9;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (dis[i][j]<=s)
for (l=1;l<=cnt;l++)
if (dis[a[l]][i]+dis[i][j]+dis[j][b[l]]==mx){//在直径上
p=0;
for (k=1;k<=n;k++)
if (k!=i && k!=j) p=max(p,(dis[k][i]+dis[k][j]-dis[i][j])>>1);
ans=min(ans,p);
}
printf("%d",ans);
}对于n<=500000。
在[SDOI2011]消防中，没说路径在直径上，可以先证一遍（出处）：
显然可以发现这条路径必然在树的直径上
至于证明，只需要假设路径Q不在直径上，那么假设距离最远的点不在直径上，易证不可能，因此距离这条路径Q最远的点一定在直径上。
之后再假设一个A点是不在直径上的一个点，我们假设直径上有一条路径P，如果A到P的距离大于了直径的端点到Q的距离，显然是矛盾的，因此任意的A点到P的距离一定小于直径端点到Q的距离，因此得证。
我反正是看不懂。。。
下面是具体实现（出处）：
先bfs两遍求出树的直径
然后维护 g[i]表示i是路径右端点时，右边那段删掉的直径长度。
f[i]表示i是路径左端点时，左边那段删掉的直径长度。
h[i]表示i是直径上的点，每个直径上的点不是都有一棵（或者很多棵）
由非此直径上点组成的树（森林）嘛，点i到这些子节点中最远的那个的距离。
然后在这个序列上跑双指针。就是路径长度不是有限制嘛，然后从左到右枚举左端点，然后右端点是非严格单调右移的。
时间复杂度线性。而对于一段路径区间[l,r]，它作为枢纽时的答案为
max(max(f[l],g[r]),max{hi,i∈[l,r]})
然后最右边那个怎么搞呢？ 单调队列，维护hi最大值
#include<bits/stdc++.h>
using namespace std;
const int N=500003;
struct node{
int to,ne,w;
}e[N*2];
int tot,num,i,s,l,r,L,R,len,f[N],g[N],h[N],tmp[N],head[N],fa[N],vis[N],q[N],n,m,x,y,z,t,be[N],ans;
inline int read(){
int x=0,f=1;char c;
do{if(c=='-')f=-1;c=getchar();}while(c>'9'||c<'0');
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
void add(int x,int y,int z){
e[++tot]=(node){y,head[x],z};
head[x]=tot;
}
int bfs(int s,int num){
int h=0,t=1,len=0;
q[1]=s;g[s]=0;fa[s]=s;vis[s]=num;
//要注意g[s]=0，每次g都重新算一遍的，不同地方的g数组可能代表的意义不同
while (h<t){
int u=q[++h];
for (int i=head[u],v;i;i=e[i].ne)
if (vis[v=e[i].to]!=num){
vis[v]=num;
g[v]=g[u]+e[i].w;
len=max(len,g[v]);
fa[v]=u;
q[++t]=v;
}
}
return len;
}
void solve(){
int s,t=0;
bfs(s=1,++num);
for (int i=1;i<=n;i++)
if (g[i]>g[s]) s=i;
bfs(s,++num);
for (int i=1;i<=n;i++)
if (g[i]>g[t]) t=i;
be[n=1]=t;num++;
do t=fa[t],be[++n]=t,vis[t]=num;while (t!=s);
for (int i=1;i<=n;i++) f[i]=g[be[1]]-g[be[i]];
for (int i=1;i<=n;i++) tmp[i]=g[be[i]];
for (int i=1;i<=n;i++) h[i]=bfs(be[i],num);
for (int i=1;i<=n;i++) g[i]=tmp[i];
}
int main(){
n=read();m=read();
for (i=1;i<n;i++){
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
solve();
ans=1e9;
for (l=1;l<=n;l++){
while (r<n && f[r+1]-f[l]<=m){
r++;
while (L<=R && h[q[R]]<h[r]) R--;
q[++R]=r;
}
ans=min(ans,max(max(f[l],g[r]),h[q[L]]));
if (q[L]<=l) L++;
}
printf("%d",ans);
}