题目
一颗\(n\)个点的树，求加入一条边点之后两点间最长距离的最小值 ；
\(n \le 100000\) ;
题解
首先加入边的两个端点一定在直径上面，先\(dfs\)拎出直径来讨论(下标只代表直径上的点)
设直径上的点\(i\)到直径起点的距离为\(s_i\)， 直径以外的子树内的最长链\(g_i\)和最大深度\(d_i\)
以 $ l = max \ { g_i } $ , $ r $ 为原树直径长度作为下界和上界，二分答案\(mid\)
只需要考虑对于所有边\((i,j)(i<j)\)，是否存在长度为\(L\)的\((a,b)(a<b)\),
使得两点间最短距离都\(<=mid\)，即使得：
\[\begin{cases}
&d_i+d_j+s_j-s_i \le mid \\
&d_i+d_j+|s_i-s_a|+|s_j-s_b|+L \le mid\\
\end{cases}
\]中存在一个成立；
若不满足1式，因为是小于等于，则展开2式绝对值
\[\begin{cases}
-s_a-s_b & \le mid-d_i-d_j-L-s_i-s_j \\
-s_a+s_b & \le mid-d_i-d_j-L-s_i+s_j \\
s_a-s_b & \le mid-d_i-d_j-L+s_i-s_j \\
s_a+s_b & \le mid-d_i-d_j-L+s_i+s_j \\
\end{cases}
\]任意一个都成立；
对\(d_i-s_i\)和\(d_i+s_i\)排序做two pointers可以得到满足(1)2的范围，分别求出(2)最紧的四个限制;
(这里已经不需要管\(i<j\)，因为如果\(i>j\)的话1不合法2一定不合法)
(2)的右边变成了定值，扫描\(s_i\)用two pointers求出四个范围，求交判断；
#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
using namespace std;
const int N=100010;
int n,o=1,hd[N],L,fa[N],A,B,st[N],tot,a[N],b[N],vis[N];
ll dis[N],s[N],d[N],g[N],f[N],mn1,mn2,lm1,lm2,lm3,lm4;
struct Edge{int v,nt,w;}E[N<<1];
char gc(){
static char*p1,*p2,ch[1000000];
if(p1==p2)p2=(p1=ch)+fread(ch,1,1000000,stdin);
return(p1==p2)?EOF:*p1++;
}//
int rd(){
int x=0;char c=gc();
while(c<'0'||c>'9')c=gc();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
return x;
}//
void adde(int u,int v,int w){
E[o]=(Edge){v,hd[u],w};hd[u]=o++;
E[o]=(Edge){u,hd[v],w};hd[v]=o++;
}//
bool cmpa(int x,int y){return d[x]-s[x]<d[y]-s[y];}//
bool cmpb(int x,int y){return d[x]+s[x]<d[y]+s[y];}//
void dfs(int u,int F){
fa[u]=F;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==F)continue;
dis[v]=dis[u]+E[i].w;
dfs(v,u);
}
}//
void chkmax(ll&x,ll y){if(x<y)x=y;}//
void chkmin(ll&x,ll y){if(x>y)x=y;}//
void cal(int u,int F){
g[u]=f[u]=0;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==F||vis[v])continue;
cal(v,u);
g[u]=max(max(g[u],g[v]),f[u]+f[v]+E[i].w);
f[u]=max(f[u],f[v]+E[i].w);
}
}//
bool check(ll mid){
mn1=mn2=lm1=lm2=lm3=lm4=inf;
for(int i=1,j=tot;i<=tot;++i){
while(j&&d[a[i]]-s[a[i]]+d[b[j]]+s[b[j]]>mid){
chkmin(mn1,-d[b[j]]-s[b[j]]);
chkmin(mn2,-d[b[j]]+s[b[j]]);
j--;
}
ll tmp=mid-d[a[i]]-L;
chkmin(lm1,tmp-s[a[i]]+mn1);
chkmin(lm2,tmp+s[a[i]]+mn1);
chkmin(lm3,tmp-s[a[i]]+mn2);
chkmin(lm4,tmp+s[a[i]]+mn2);
}
int j1=tot+1,j2=1,j3=0,j4=tot;
for(int i=1;i<=tot;++i){
while(j1>1&&-s[i]-s[j1-1]<=lm1)j1--;
while(j2<=tot&&s[i]-s[j2]>lm2)j2++;
while(j3<tot&&-s[i]+s[j3+1]<=lm3)j3++;
while(j4>=1&&s[i]+s[j4]>lm4)j4--;
int l=max(j1,j2),r=min(j3,j4);
if(l<=r)return true;
}
return false;
}
int main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
while(1){
n=rd();L=rd();o=1;tot=0;
if(!n&&!L)break;
for(int i=1;i<=n;++i)hd[i]=0;
for(int i=1,u,v,w;i<n;++i){u=rd(),v=rd(),w=rd();adde(u,v,w);}
dis[A=1]=0;dfs(1,0);
for(int i=1;i<=n;++i)if(dis[i]>dis[A])A=i;
dis[B=A]=0;dfs(A,0);
for(int i=1;i<=n;++i)if(dis[i]>dis[B])B=i;
cal(1,0);
ll r=g[1],l=0;
for(int i=B;i;i=fa[i])st[++tot]=i,vis[i]=1;
reverse(st+1,st+tot+1);
for(int i=1;i<=tot;++i){
a[i]=b[i]=i;
cal(st[i],0);
d[i]=f[st[i]];
s[i]=dis[st[i]];
l=max(l,g[st[i]]);
}
for(int i=1;i<=tot;++i)vis[st[i]]=0;
sort(a+1,a+tot+1,cmpa);
sort(b+1,b+tot+1,cmpb);
while(l<r){
ll mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld\n",l);
}//
return 0;
}