【loj2262】【CTSC2017】网络

佚名 6年前 (2019-05-07) 随笔 918人围观抢沙发百度已收录

题目

一颗$n$个点的树，求加入一条边点之后两点间最长距离的最小值；

$n \le 100000$ ;

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

首先加入边的两个端点一定在直径上面，先$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;
}