一棵树，有边权。你需要加一条长度固定、点没有固定的边进去，使得两两点之间最大距离最小。问这个最小的最大距离。
(nle 10^5)
手玩一下可以猜到加入的边两个端点一定在直径上。证明大概考虑如果不是加在直径上可以调整使其更优。于是我证了几种情况就懒得继续分类讨论下去了，不知道有没有路过的大佬指点一下比较简洁的做法。
求出直径上挂着的子树内部的直径长度，这些是不可避免的，要作为下界。上界为直径长度。二分答案、
问题：设(p_i)为前缀和，(d_i)表示(i)点往下伸的最长长度。需要找到一对点(u<v)，使得对于任意(x<y)满足一下条件之一：
- (d_y+d_x+p_y-p_xle ans)
- (d_y+d_x+|p_y-p_v|+|p_x-p_u|le ans)。拆掉绝对值分成四条式子，要求这些式子都满足。
于是可以排序+树状数组得到(pm p_upm p_v)的最紧的限制。最后的问题是找到合适的(u,v)。枚举(u)，发现对于四个限制(v)都是个前缀或后缀，并且都是随(u)增大而单调变化的。用四个指针搞一搞即可。
(O(nlg nlg R))
using namespace std;
#include <bits/stdc++.h>
#define N 100005
#define ll long long
int n,K;
struct EDGE{
int to,w;
EDGE *las;
} e[N*2];
int ne;
EDGE *last[N];
void link(int u,int v,int w){
e[ne]={v,w,last[u]};
last[u]=e+ne++;
}
int fa[N],len[N];
ll dis[N];
void getdis(int x){
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->to!=fa[x]){
fa[ei->to]=x;
len[ei->to]=ei->w;
dis[ei->to]=dis[x]+ei->w;
getdis(ei->to);
}
}
ll f[N],g[N];
int tot;
ll p[N],d[N];
ll L,R;
void dp(int x,int ban=0){
f[x]=g[x]=0;
ll fir=0,sec=0;
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->to!=fa[x] && ei->to!=ban){
dp(ei->to);
g[x]=max(g[x],g[ei->to]);
ll t=f[ei->to]+ei->w;
f[x]=max(f[x],t);
if (t>fir)
sec=fir,fir=t;
else if (t>sec)
sec=t;
}
g[x]=max(g[x],fir+sec);
}
void init(){
fa[1]=0,dis[1]=0,getdis(1);
int S=1;
for (int i=2;i<=n;++i)
if (dis[i]>dis[S])
S=i;
fa[S]=0,dis[S]=0,getdis(S);
int T=1;
for (int i=2;i<=n;++i)
if (dis[i]>dis[T])
T=i;
L=0;
R=dis[T];
p[tot=1]=0;
for (int x=fa[T],y=T;x;y=x,x=fa[x]){
++tot;
p[tot]=p[tot-1]+len[y];
dp(x,y);
d[tot]=f[x];
L=max(L,g[x]);
}
}
#define INF (1ll<<50)
int q0[N],q1[N];
bool cmp0(int x,int y){return d[x]+p[x]<d[y]+p[y];}
bool cmp1(int x,int y){return d[x]-p[x]<d[y]-p[y];}
struct TA{
ll t[N];
void init(){
for (int i=1;i<=tot;++i)
t[i]=INF;
}
void ins(int x,ll c){
for (;x<=tot;x+=x&-x)
t[x]=min(t[x],c);
}
ll query(int x){
ll r=INF;
for (;x;x-=x&-x)
r=min(r,t[x]);
return r;
}
} ta[2];
bool judge(ll ans){
ta[0].init();
ta[1].init();
ll lim[4]={INF,INF,INF,INF};
for (int j=1,i=tot;j<=tot;++j){
for (;i>=1 && d[q0[j]]+p[q0[j]]+d[q1[i]]-p[q1[i]]>ans;--i){
ta[0].ins(q1[i],-d[q1[i]]+p[q1[i]]);
ta[1].ins(q1[i],-d[q1[i]]-p[q1[i]]);
}
lim[0]=min(lim[0],ans-K-d[q0[j]]+p[q0[j]]+ta[0].query(q0[j]-1));
lim[1]=min(lim[1],ans-K-d[q0[j]]+p[q0[j]]+ta[1].query(q0[j]-1));
lim[2]=min(lim[2],ans-K-d[q0[j]]-p[q0[j]]+ta[0].query(q0[j]-1));
lim[3]=min(lim[3],ans-K-d[q0[j]]-p[q0[j]]+ta[1].query(q0[j]-1));
}
p[0]=-INF,p[tot+1]=INF;
int q[4]={tot,1,1,tot};
for (int i=1;i<tot;++i){
for (;q[0]>=1 && +p[i]+p[q[0]]>lim[0];--q[0]);
for (;q[2]<=tot && +p[i]-p[q[2]]>lim[2];++q[2]);
for (;q[1]<=tot && -p[i]+p[q[1]]<=lim[1];++q[1]);
for (;q[3]>=1 && -p[i]-p[q[3]]<=lim[3];--q[3]);
int r=min(q[0],q[1]-1),l=max(max(q[2],q[3]+1),i+1);
if (l<=r)
return 1;
}
// for (int i=1;i<tot;++i)
// for (int j=i+1;j<=tot;++j){
// if (+p[i]+p[j]<=lim[0] &&
// -p[i]+p[j]<=lim[1] &&
// +p[i]-p[j]<=lim[2] &&
// -p[i]-p[j]<=lim[3])
// return 1;
// }
return 0;
}
ll work(){
for (int i=1;i<=tot;++i)
q0[i]=q1[i]=i;
sort(q0+1,q0+tot+1,cmp0);
sort(q1+1,q1+tot+1,cmp1);
ll res=-1;
while (L<=R){
ll mid=L+R>>1;
if (judge(mid))
R=(res=mid)-1;
else
L=mid+1;
}
return res;
}
int main(){
freopen("in.txt","r",stdin);
while (1){
scanf("%d%d",&n,&K);
if (n==0 && K==0)
return 0;
ne=0;
memset(last,0,sizeof(EDGE*)*(n+1));
for (int i=1;i<n;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
link(u,v,w),link(v,u,w);
}
init();
ll ans=work();
printf("%lld
",ans);
}
return 0;
}