1 #include
     
        2 #include
      
         3 #include
       
          4 #define N 600000  5 using namespace std;  6 int cnt,n,s,head[N],next[N*2],u[N*2],v[N*2],q[N],h,t,d[N],f[N],mx,rt1,mx1,from[N],zhan[N],tot,mark[N];  7 int l,r,ans;  8 void jia(int a1,int a2,int a3)  9 { 10     cnt++; 11     next[cnt]=head[a1]; 12     head[a1]=cnt; 13     u[cnt]=a2; 14     v[cnt]=a3; 15     return; 16 } 17 bool pan(int a1) 18 { 19     int L=1,R=tot; 20     for(;zhan[1]-zhan[L]<=a1;L++); 21     for(;zhan[R]-zhan[tot]<=a1;R--); 22     if(zhan[L-1]-zhan[R+1]>s) 23       return 0; 24     return 1; 25 } 26 void dfs(int a1) 27 { 28     h=0; 29     t=1; 30     q[t]=a1; 31     memset(f,0,sizeof(f)); 32     f[a1]=1; 33     d[a1]=0; 34     for(;h
        
         l) 90         l=d[i]; 91     for(;l<=r;) 92       { 93         int mid=(l+r)>>1; 94         if(pan(mid)) 95           { 96             ans=mid; 97             r=mid-1; 98           } 99         else100           l=mid+1;101       }102     printf("%d\n",ans);103     return 0;104 }
        
       
      
     

显然最长距离最短，一定是在直径上，我们先DFS两遍找出直径，把直径上的边赋值成0，跑一遍dfs,找一个最大值作为l，二分答案判断。