Description
某个国家有\(n\)个城市，这\(n\)个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为\(z_i(z_i<=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
【样例输入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\)。
Solution
- 有一个性质:这样的路径一定是直径上的某一段.
- 那么先通过两次\(bfs\)找出直径,二分答案.
- 根据二分的答案在直径两侧向内取,取出后验证长度是否小于等于\(s\).
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int MAXN=3e5+10;
int n,s;
int cnt=0,head[MAXN];
int nx[MAXN<<1],to[MAXN<<1],val[MAXN<<1];
inline void add(int u,int v,int w)
{
++cnt;
to[cnt]=v;
nx[cnt]=head[u];
val[cnt]=w;
head[u]=cnt;
}
int dis[MAXN],pre[MAXN];
int marked[MAXN];
void bfs(int rt)
{
memset(dis,-1,sizeof dis);
dis[rt]=0;
queue<int> q;
q.push(rt);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nx[i])
{
int v=to[i];
if(dis[v]!=-1)
continue;
pre[v]=u;
if(marked[v])
dis[v]=dis[u];
else
dis[v]=dis[u]+val[i];
q.push(v);
}
}
}
int top=0,st[MAXN];
int check(int d)
{
int l=1,r=top;
while(st[1]-st[l+1]<=d && l<=top)
++l;
while(st[r-1]<=d && r>=1)
--r;
return st[l]-st[r]<=s;
}
int main()
{
n=read(),s=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w);
add(v,u,w);
}
int rt=0,x=0;
bfs(1);
for(int i=1;i<=n;++i)
if(dis[rt]<dis[i])
rt=i;
bfs(rt);
for(int i=1;i<=n;++i)
if(dis[x]<dis[i])
x=i;//from rt to x
int L=0,R=dis[x];
st[++top]=dis[x];
marked[x]=1;
while(x!=rt)
{
st[++top]=dis[pre[x]];
x=pre[x];
marked[x]=1;
}
bfs(x);
for(int i=1;i<=n;++i)
L=max(L,dis[i]);
if(s<R)
{
while(L<=R)
{
int mid=(L+R)>>1;
if(check(mid))
R=mid-1;
else
L=mid+1;
}
}
printf("%d\n",L);
return 0;
}