Description
某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。
Input
输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
Output
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
Sample Input
【样例输入1】
5 2
1 2 5
2 3 2
2 4 4
2 5 3
【样例输出1】
5
【样例输入2】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
【样例输出2】
5
Sample Output
HINT
【数据规模和约定】
对于20%的数据，n<=300。
对于50%的数据，n<=3000。
对于100%的数据，n<=300000，边长小等于1000。
【思路】
树的直径，二分法
可以知道题目要找的路径一定是树的直径的一段。对于这段在树上的路径，到达它的最大值有两种情况:一种是到达路径端点，这时候最大值为树的直径的两端取较大；另一种是和路径上除端点外的节点相连。
求出其他节点到直径的最大值mx，则答案一定不小于该最大值，并以之为下界二分直径端点到路径端点的距离，取最小。
【代码】
1 #include<queue> 2 #include<cstdio> 3 #include<vector> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 8 using namespace std; 9 10 const int N = 3*1e5+10; 11 const int INF = 1e9; 12 13 struct Edge{ int v,w; }; 14 vector<Edge> g[N]; 15 int n,S,que[N],qz,dis[N],mark[N],fa[N]; 16 17 void read(int& x) { 18 char c=getchar(); int f=1; x=0; 19 while(!isdigit(c)) {if(c=='-')f=-1; c=getchar();} 20 while(isdigit(c)) x=x*10+c-'0',c=getchar(); 21 x*=f; 22 } 23 24 queue<int> q; 25 void bfs(int u) { 26 q.push(u); fa[u]=-1; 27 FOR(i,1,n) dis[i]=INF; dis[u]=0; 28 while(!q.empty()) { 29 int u=q.front(); q.pop(); 30 for(int i=0;i<g[u].size();i++) { 31 int v=g[u][i].v; 32 if(v!=fa[u]) { 33 fa[v]=u; q.push(v); 34 if(mark[v]) dis[v]=dis[u]; 35 else dis[v]=min(dis[v],dis[u]+g[u][i].w); 36 } 37 } 38 } 39 } 40 bool can(int ML) { 41 int l=1,r=qz; 42 while(l<=qz && que[1]-que[l+1]<=ML) l++; 43 while(r && que[r-1]-que[qz]<=ML) r--; 44 return que[l]-que[r]<=S; 45 } 46 47 int main() { 48 read(n),read(S); 49 int u,v,w,x=1,y=1,dist,L=0,R=0,M; 50 FOR(i,1,n-1) { 51 read(u),read(v),read(w); 52 g[u].push_back((Edge){v,w}); 53 g[v].push_back((Edge){u,w}); 54 } 55 bfs(1); FOR(i,1,n) if(dis[i]>dis[x]) x=i; 56 bfs(x); FOR(i,1,n) if(dis[i]>dis[y]) y=i; 57 int t=y; R=dis[y]-dis[x]; 58 while(t!=x) { 59 que[++qz]=dis[t]; mark[t]=1; 60 t=fa[t]; 61 } 62 que[++qz]=dis[t]; 63 bfs(x); 64 FOR(i,1,n) L=max(L,dis[i]); 65 while(L<R) { 66 M=(L+R)>>1; 67 if(can(M)) R=M; else L=M+1; 68 } 69 printf("%d",L); 70 return 0; 71 }