题目描述
某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于*对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。
输入输出格式
输入格式：
输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出格式：
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
输入输出样例
说明
【数据规模和约定】
对于20%的数据，n<=300。
对于50%的数据，n<=3000。
对于100%的数据，n<=300000，边长小等于1000。
最重要的一点就是路径一定全都在树的直径上，至于证明就自行百度吧嘿嘿：
确定直径的两个端点 l 和 r ，维护直径上的每个点到达的最远的点的距离（不包括直径上的点),要么二分最大值，把两个端点向里缩mid，判断距离两个端点之间的点（不包括端点，因为到一个点最远的点一定是直径的一个端点）最远的距离是否大于mid，和 两个端点之间的距离是否小于题目的条件s；
或者是维护单调不增的队列，路径越长越好，维护头尾的距离不超过s，取ans=min(ans,max(q[头],max( dis[头],dis[端点】-dis[尾}))
只有二分的码qwq：
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #include<iostream> 6 using namespace std; 7 const int N=2000001; 8 struct node{ 9 int to,nex,v; 10 }e[N<<1]; 11 int dep[N],dis[N],vis[N],ff[N],son[N]; 12 int maxn,s,t,n,k,l,r; 13 int num,head[N]; 14 15 void add(int from,int to,int v){ 16 num++; 17 e[num].to=to; 18 e[num].v=v; 19 e[num].nex=head[from]; 20 head[from]=num; 21 } 22 23 int read(){ 24 int x=0,w=1;char ch=getchar(); 25 while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();} 26 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 27 return x*w; 28 } 29 30 void dfs(int x,int fa){ 31 for(int i=head[x];i;i=e[i].nex){ 32 int v=e[i].to;if(v==fa)continue;ff[v]=x; 33 dis[v]=dis[x]+e[i].v;dfs(v,x); 34 } 35 } 36 37 void dfs2(int x){ 38 dep[x]=0;int maxx=0; 39 for(int i=head[x];i;i=e[i].nex){ 40 int v=e[i].to;if(v==ff[x]||vis[v])continue; 41 dfs2(v);maxx=max(maxx,e[i].v+dep[v]); 42 } 43 dep[x]=maxx; 44 } 45 46 bool judge(int mid){ 47 int sum=0,sum1=0,sum2=0,ll=s,rr=t; 48 while(sum1-dis[ll]+dis[son[ll]]<=mid&&ll!=rr&&ll){ 49 sum1+=dis[son[ll]]-dis[ll];ll=son[ll]; 50 } 51 while(sum2+dis[rr]-dis[ff[rr]]<=mid&&rr!=ll&&rr){ 52 sum2+=dis[rr]-dis[ff[rr]];rr=ff[rr]; 53 } 54 //if(dis[rr]<dis[ll])return false; 55 while(rr!=ll) 56 {sum+=dis[rr]-dis[ff[rr]]; 57 if(dep[rr]>mid)return false; 58 rr=ff[rr]; 59 } 60 if(dep[ll]>mid)return false; 61 if(sum>k)return false; 62 return true; 63 } 64 65 int main(){ 66 n=read();k=read(); 67 for(int i=1;i<n;i++){ 68 int x=read(),y=read(),z=read(); 69 add(x,y,z);add(y,x,z);r+=z; 70 } 71 dfs(1,0);for(int i=1;i<=n;i++){if(dis[i]>maxn)maxn=dis[i],s=i;ff[i]=dis[i]=0;} 72 dfs(s,0);maxn=0; 73 for(int i=1;i<=n;i++){if(dis[i]>maxn)maxn=dis[i],t=i;} 74 int now=t; 75 while(now){ 76 vis[now]=1;son[ff[now]]=now;now=ff[now]; 77 } 78 now=t; 79 while(now!=ff[s]){ 80 dfs2(now); 81 now=ff[now]; 82 } 83 while(r>l){ 84 int mid=(l+r)>>1; 85 if(judge(mid))r=mid; 86 else l=mid+1; 87 } 88 printf("%d\n",l); 89 return 0; 90 }
1