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
5 2
1 2 5
2 3 2
2 4 4
2 5 3
【样例输入2】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
Sample Output
【样例输出1】
5
【样例输出2】
5
HINT
对于100%的数据，n<=300000，边长小等于1000。
Source
首先我们应该想到这条路径一定在树的直径上。这里给出证明：
设直径的长度为d，那么直径外的边长度一定小于等于d/2（否则该路径会与直径的一部分构成一条比直径还长的路径）
若该路径不在直径上，则直径的最远点到该路径的距离至少为d/2
而如果在直径上，一定存在一段路径使得树上所有点的距离到它不超过d/2
所以选在直径上一定是优的，而且在符合题目要求的情况下越长越好。
那么如果我们确定里直径，我们可以O(n)求出直径上每个点到最远点的距离，然后左右指针扫直径，单调队列维护区间最小值即可。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
deque<int>q;
struct point
{
int to;
int next;
int dis;
}e[];
int n,x,y,z,res=,maxn,s,t,num,ss;
int d[],head[],f[],pre[];
bool vis[];
void add(int from,int to,int dis)
{
e[++num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num;
}
void dfs(int x)
{
vis[x]=true;
for(int i=head[x];i!=;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
d[to]=d[x]+e[i].dis;
dfs(to);
}
}
}
void dfs1(int x)
{
vis[x]=true;
for(int i=head[x];i!=;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
pre[to]=x;
d[to]=d[x]+e[i].dis;
dfs1(to);
}
}
}
void find(int x)
{
vis[x]=true;
for(int i=head[x];i!=;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
find(to);
d[x]=max(d[x],d[to]+e[i].dis);
}
}
}
void getf()
{
int slr=;
for(int i=t;i!=;i=pre[i])
{
f[i]=slr;
for(int j=head[i];j!=;j=e[j].next)
{
int to=e[j].to;
if(pre[i]==to)
{
slr+=e[j].dis;
break;
}
}
}
}
int main()
{
scanf("%d%d",&n,&ss);
for(int i=;i<=n-;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs();
for(int i=;i<=n;i++)
{
if(d[i]>maxn)
{
maxn=d[i];
s=i;
}
}
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));
dfs1(s);
maxn=;
for(int i=;i<=n;i++)
if(d[i]>maxn)
{
maxn=d[i];
t=i;
}
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));
for(int i=t;i!=;i=pre[i])
vis[i]=true;
for(int i=t;i!=;i=pre[i])
find(i);
getf();
int r=t,l=pre[t];
q.push_front(l);
if(d[l]<d[r])
q.push_back(r);
while()
{
if(pre[l]!=&&f[pre[l]]-f[r]<=ss)
{
l=pre[l];
int ans=max(f[r],maxn-f[l]);
q.push_front(l);
while(d[q.back()]<d[l])
q.pop_back();
ans=max(ans,d[q.back()]);
res=min(res,ans);
}
else if(l!=r)
{
if(q.back()==r)
q.pop_back();
r=pre[r];
int ans=max(f[r],maxn-f[l]);
ans=max(ans,d[q.back()]);
res=min(res,ans);
}
else if(l==r&&pre[l])
{
while(!q.empty())
q.pop_back();
l=pre[l];
r=l;
q.push_front(l);
int ans=max(f[r],maxn-f[l]);
ans=max(ans,d[q.back()]);
res=min(res,ans);
}
else
break;
}
printf("%d",res);
return ;
}
这道题综合了许多算法，也有一定的思维难度，是一道不可多得好题