输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
对于100%的数据，n<=300000，边长小等于1000。
首先我们应该想到这条路径一定在树的直径上。这里给出证明：
设直径的长度为d，那么直径外的边长度一定小于等于d/2（否则该路径会与直径的一部分构成一条比直径还长的路径）
若该路径不在直径上，则直径的最远点到该路径的距离至少为d/2
而如果在直径上，一定存在一段路径使得树上所有点的距离到它不超过d/2
所以选在直径上一定是优的，而且在符合题目要求的情况下越长越好。
那么如果我们确定里直径，我们可以O(n)求出直径上每个点到最远点的距离，然后左右指针扫直径，单调队列维护区间最小值即可。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 deque<int>q; 7 struct point 8 { 9 int to; 10 int next; 11 int dis; 12 }e[1000010]; 13 int n,x,y,z,res=100000010,maxn,s,t,num,ss; 14 int d[500001],head[500001],f[500001],pre[500001]; 15 bool vis[500001]; 16 void add(int from,int to,int dis) 17 { 18 e[++num].next=head[from]; 19 e[num].to=to; 20 e[num].dis=dis; 21 head[from]=num; 22 } 23 void dfs(int x) 24 { 25 vis[x]=true; 26 for(int i=head[x];i!=0;i=e[i].next) 27 { 28 int to=e[i].to; 29 if(!vis[to]) 30 { 31 d[to]=d[x]+e[i].dis; 32 dfs(to); 33 } 34 } 35 } 36 void dfs1(int x) 37 { 38 vis[x]=true; 39 for(int i=head[x];i!=0;i=e[i].next) 40 { 41 int to=e[i].to; 42 if(!vis[to]) 43 { 44 pre[to]=x; 45 d[to]=d[x]+e[i].dis; 46 dfs1(to); 47 } 48 } 49 } 50 void find(int x) 51 { 52 vis[x]=true; 53 for(int i=head[x];i!=0;i=e[i].next) 54 { 55 int to=e[i].to; 56 if(!vis[to]) 57 { 58 find(to); 59 d[x]=max(d[x],d[to]+e[i].dis); 60 } 61 } 62 } 63 void getf() 64 { 65 int slr=0; 66 for(int i=t;i!=0;i=pre[i]) 67 { 68 f[i]=slr; 69 for(int j=head[i];j!=0;j=e[j].next) 70 { 71 int to=e[j].to; 72 if(pre[i]==to) 73 { 74 slr+=e[j].dis; 75 break; 76 } 77 } 78 } 79 } 80 int main() 81 { 82 scanf("%d%d",&n,&ss); 83 for(int i=1;i<=n-1;i++) 84 { 85 scanf("%d%d%d",&x,&y,&z); 86 add(x,y,z); 87 add(y,x,z); 88 } 89 dfs(1); 90 for(int i=1;i<=n;i++) 91 { 92 if(d[i]>maxn) 93 { 94 maxn=d[i]; 95 s=i; 96 } 97 } 98 memset(vis,false,sizeof(vis)); 99 memset(d,0,sizeof(d)); 100 dfs1(s); 101 maxn=0; 102 for(int i=1;i<=n;i++) 103 if(d[i]>maxn) 104 { 105 maxn=d[i]; 106 t=i; 107 } 108 memset(vis,false,sizeof(vis)); 109 memset(d,0,sizeof(d)); 110 for(int i=t;i!=0;i=pre[i]) 111 vis[i]=true; 112 for(int i=t;i!=0;i=pre[i]) 113 find(i); 114 getf(); 115 int r=t,l=pre[t]; 116 q.push_front(l); 117 if(d[l]<d[r]) 118 q.push_back(r); 119 while(1) 120 { 121 if(pre[l]!=0&&f[pre[l]]-f[r]<=ss) 122 { 123 l=pre[l]; 124 int ans=max(f[r],maxn-f[l]); 125 q.push_front(l); 126 while(d[q.back()]<d[l]) 127 q.pop_back(); 128 ans=max(ans,d[q.back()]); 129 res=min(res,ans); 130 } 131 else if(l!=r) 132 { 133 if(q.back()==r) 134 q.pop_back(); 135 r=pre[r]; 136 int ans=max(f[r],maxn-f[l]); 137 ans=max(ans,d[q.back()]); 138 res=min(res,ans); 139 } 140 else if(l==r&&pre[l]) 141 { 142 while(!q.empty()) 143 q.pop_back(); 144 l=pre[l]; 145 r=l; 146 q.push_front(l); 147 int ans=max(f[r],maxn-f[l]); 148 ans=max(ans,d[q.back()]); 149 res=min(res,ans); 150 } 151 else 152 break; 153 } 154 printf("%d",res); 155 return 0; 156 }
这道题综合了许多算法，也有一定的思维难度，是一道不可多得好题
原文：https://www.cnblogs.com/Slrslr/p/9397895.html