输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
对于100%的数据，n<=300000，边长小等于1000。
题解：
有一个结论：树的任意一条直径上一定存在最优路径，即使树的直径不止一条。
这样，我们可以两边DFS求出树的一条直径，然后把树的直径上的点排成队列，记录从这些点向外（即不沿直径的两个方向）所能走到的最远距离。
让左右端点在队列上移动，表示所选的区间。当右端点确定时，左端点要尽量靠左（即路径要尽量长）才更优，但长度不能超过限定。
选择这样的一条路径的最远距离即为左端点到直径一端的距离、路径上点向外走出的最远距离（我用了线段树，事实上可以利用直径的性质O(1)记录）、右端点到直径另一端的距离的最大值。
代码：
1 uses math; 2 var 3 i,j,k,l,n,m,s,rt,len,nn,cnt,ans:longint; 4 b:array[0..600001,0..2]of longint; 5 dis,c,dis2,dis3,fx,a,lb:array[0..300001]of longint; 6 t:array[0..600001,-2..2]of longint; 7 procedure ss(x,fa:longint); 8 var i:longint; 9 begin 10 i:=c[x]; 11 while i>0 do 12 begin 13 if b[i,1]<>fa then 14 begin dis[b[i,1]]:=dis[x]+b[i,0]; ss(b[i,1],x); end; 15 i:=b[i,2]; 16 end; 17 end; 18 procedure ss2(x,fa:longint); 19 var i:longint; 20 begin 21 i:=c[x]; 22 while i>0 do 23 begin 24 if b[i,1]<>fa then 25 begin 26 dis[b[i,1]]:=dis[x]+b[i,0]; 27 ss2(b[i,1],x); 28 if dis2[b[i,1]]+b[i,0]>dis2[x] then 29 begin dis2[x]:=dis2[b[i,1]]+b[i,0]; fx[x]:=i; end; 30 end; 31 i:=b[i,2]; 32 end; 33 i:=c[x]; 34 while i>0 do 35 begin 36 if(b[i,1]<>fa)and(i<>fx[x])then 37 dis3[x]:=max(dis3[x],dis2[b[i,1]]+b[i,0]); 38 i:=b[i,2]; 39 end; 40 end; 41 procedure ss3(x:longint); 42 var i:longint; 43 begin 44 inc(nn); a[nn]:=dis3[x]; lb[nn]:=x; 45 if fx[x]>0 then ss3(b[fx[x],1]); 46 end; 47 procedure build(l,r,fa:longint); 48 var x:longint; 49 begin 50 inc(cnt); x:=cnt; 51 t[x,1]:=l; t[x,2]:=r; 52 if t[x,1]=t[fa,1] then t[fa,-1]:=x else t[fa,-2]:=x; 53 if l=r then begin t[x,0]:=a[l]; exit; end; 54 build(l,(l+r)div 2,x); build((l+r)div 2+1,r,x); 55 t[x,0]:=max(t[t[x,-1],0],t[t[x,-2],0]); 56 end; 57 function qq(x,l,r:longint):longint; 58 var ll,rr:longint; 59 begin 60 ll:=t[x,1]; rr:=t[x,2]; 61 if(ll=l)and(rr=r)then exit(t[x,0]); 62 if r<=(ll+rr)div 2 then exit(qq(t[x,-1],l,r)); 63 if l>(ll+rr)div 2 then exit(qq(t[x,-2],l,r)); 64 exit(max(qq(t[x,-1],l,(ll+rr)div 2),qq(t[x,-2],(ll+rr)div 2+1,r))); 65 end; 66 begin 67 readln(n,s); 68 for i:=2 to n do 69 begin 70 readln(j,k,l); 71 inc(m); b[m,1]:=k; b[m,0]:=l; b[m,2]:=c[j]; c[j]:=m; 72 inc(m); b[m,1]:=j; b[m,0]:=l; b[m,2]:=c[k]; c[k]:=m; 73 end; 74 ss(1,0); rt:=1; 75 for i:=2 to n do if dis[i]>dis[rt] then rt:=i; 76 dis[rt]:=0; ss2(rt,0); ss3(rt); len:=dis2[rt]; 77 build(1,nn,0); 78 j:=1; ans:=maxlongint; 79 for i:=1 to nn do 80 begin 81 while dis[lb[i]]-dis[lb[j]]>s do inc(j); 82 ans:=min(ans,max(max(dis[lb[j]],dis2[lb[i]]),qq(1,j,i))); 83 end; 84 writeln(ans); 85 end.
原文：http://www.cnblogs.com/GhostReach/p/6308650.html
