我们总是在刷那些常考的算法，却忽略一些冷门算法，以至于一涉及这些就不会。
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\)——题记
读本章所需思维：反证法
定义：树上任意两节点之间最长的简单路径即为树的「直径」
显然，一棵树可以有多条「直径」
一些引理（这里只讨论边权没有负的情况）：
·\(1\)，所有「直径」的中点是同一个
证明：考虑经过的不是同一点，那么一条「直径」的一端到该「直径」的中点再到另一个「直径」的中点再到另一个「直径」的一端一定更优，所以矛盾，古该结论成立。
·\(2\)，从任意节点开始 \(dfs\)，到达的最远节点，必然是直径的一端。
证明：考虑反证法，易证
观察题目，我们发现：要找长度和不超过 \(s\) 的路径，所以我们无法树形 \(DP\)（或者说很难）。
那竟然无法从条件入手，那就从目的入手：要求其他所有城市到这条路径的距离的最大值最小，所以我们要找这条路径的性质。
我们发现，这条路径必然包含一些点，因为到这些点最远的点就是树的「直径」的一端，所以我们找的点一定要尽可能接近树的「直径」的两端，所以可以得知这条路被树的「直径」包含。
因为「直径」有多条，考虑找任意一条即可，证明仔细思考即可，很难写
至于找路径可以用单调栈实现
上代码：
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=3e5+50;
int n,s,ans=1e9;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dis[N],pre[N],xl[N];
void dfs(int wz,int last,int cd,bool flag)
{
if(flag) pre[wz]=last,xl[wz]=cd;
dis[wz]=dis[last]+cd;
for(int i=h[wz];i!=-1;i=ne[i])
if(e[i]!=last) dfs(e[i],wz,w[i],flag);
}
int st,en;
void Get_road()
{
dfs(1,0,0,0);
for(int i=1,maxdis=0;i<=n;i++)
if(dis[i]>maxdis) maxdis=dis[i],st=i;
dfs(st,0,0,1);
for(int i=1,maxdis=0;i<=n;i++)
if(dis[i]>maxdis) maxdis=dis[i],en=i;
}
int dis1[N];
void bfs()
{
memset(dis,0x3f,sizeof dis);
queue<int> q,from;
for(int i=en;i!=0;i=pre[i])
q.push(i),from.push(i),dis[i]=0;
while(!q.empty())
{
int wz=q.front(),fr=from.front();
q.pop(),from.pop();
for(int i=h[wz];i!=-1;i=ne[i])
if(dis[e[i]]==dis[0])
{
dis[e[i]]=dis[wz]+w[i];
dis1[fr]=max(dis1[fr],dis[e[i]]);
q.push(e[i]);
from.push(fr);
}
}
}
PII que[N];
int sum[N],ks=1,js;
void solve()
{
for(int i=en;i!=st;i=pre[i])//
sum[pre[i]]=sum[i]+xl[i];
for(int l=en,r=en;r!=st&&l!=0;l=pre[l])
{
int last=r;
while(sum[r]-sum[l]<=s&&r!=0)
{
last=r,r=pre[r];
if(r!=0&&sum[r]-sum[l]<=s)
{
while(js>=ks&&dis1[r]>=que[js].first) js--;
que[++js]={dis1[r],r};
}
}
if(r==0||sum[r]-sum[l]>s) r=last;
int now=max(sum[l],sum[st]-sum[r]);
now=max(now,que[ks].first);
ans=min(now,ans);
if(que[ks].second==l) ks++;
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d %d",&n,&s);
int u,v,w;
for(int i=1;i<n;i++)
{
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
Get_road();
bfs();
solve();
printf("%d\n",ans);
return 0;
}
没有一个算法值得轻视，也没有一个算法简单
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\)——后记