#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=1e5+6; int n,s,dis[N],fa[N],flag[N],far,ans=2e9; struct edge{ int to,w; }; vector<edge> G[N]; void dfs(int u,int f){ fa[u]=f; if(dis[u]>dis[far])far=u;//记录最远的距离 for(int i=0;i<G[u].size();i++){ int v=G[u][i].to, w=G[u][i].w; if(v==f||flag[v])continue; dis[v]=dis[u]+w; dfs(v,u); } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=2,u,v,w;i<=n;i++){ cin>>u>>v>>w; G[u].push_back((edge){v,w}); G[v].push_back((edge){u,w}); } int A,B; //直径的两端 dis[1]=1;dfs(1,0);A=far; //第一次dfs dis[far]=0;dfs(far,0);B=far; //第二次dfs for(int i=B,j=B; i; i=fa[i]){ while(dis[j]-dis[i]>s)j=fa[j]; //双指针法（尺取法） int x=max(dis[B]-dis[j], dis[i]); ans=min(ans,x); } for(int i=B; i; i=fa[i])flag[i]=1; //直径上的点跳过 for(int i=B; i; i=fa[i]){ dis[i]=0; dfs(i,fa[i]); //计算直径上每个点可以访问的最远距离 （可以有多条直径 } for(int i=1;i<=n;i++) ans=max(ans,dis[i]); //得到所有点可以访问最远距离的最大值 cout<<ans; return 0; }

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=1e5+6; int n,s,dis[N],fa[N],flag[N],far,ans=2e9; struct edge{ int to,w; }; vector<edge> G[N]; void dfs(int u,int f){ fa[u]=f; if(dis[u]>dis[far])far=u; for(int i=0;i<G[u].size();i++){ int v=G[u][i].to, w=G[u][i].w; if(v==f||flag[v])continue; dis[v]=dis[u]+w; dfs(v,u); } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=2,u,v,w;i<=n;i++){ cin>>u>>v>>w; G[u].push_back((edge){v,w}); G[v].push_back((edge){u,w}); } int A,B; dis[1]=1;dfs(1,0);A=far; dis[far]=0;dfs(far,0);B=far; for(int i=B,j=B; i; i=fa[i]){ while(dis[j]-dis[i]>s)j=fa[j]; int x=max(dis[B]-dis[j], dis[i]); ans=min(ans,x); } for(int i=B; i; i=fa[i])flag[i]=1; for(int i=B; i; i=fa[i]){ dis[i]=0; dfs(i,fa[i]); } for(int i=1;i<=n;i++) ans=max(ans,dis[i]); cout<<ans; return 0; }

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=1e5+6; int n,s,dis[N],fa[N],flag[N],far,ans=2e9; struct edge{ int to,w; }; vector<edge> G[N]; void dfs(int u,int f){ fa[u]=f; if(dis[u]>dis[far])far=u;//记录最远的距离 for(int i=0;i<G[u].size();i++){ int v=G[u][i].to, w=G[u][i].w; if(vf||flag[v])continue; dis[v]=dis[u]+w; dfs(v,u); } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=2,u,v,w;i<=n;i++){ cin>>u>>v>>w; G[u].push_back((edge){v,w}); G[v].push_back((edge){u,w}); } int A,B; //直径的两端 dis[1]=1;dfs(1,0);A=far; //第一次dfs dis[far]=0;dfs(far,0);B=far; //第二次dfs for(int i=B,j=B; i; i=fa[i]){ while(dis[j]-dis[i]>s)j=fa[j]; //双指针法（尺取法） int x=max(dis[B]-dis[j], dis[i]); ans=min(ans,x); } for(int i=B; i; i=fa[i])flag[i]=1; //直径上的点跳过 for(int i=B; i; i=fa[i]){ dis[i]=0; dfs(i,fa[i]); //计算直径上每个点可以访问的最远距离 （可以有多条直径 } for(int i=1;i<=n;i++) ans=max(ans,dis[i]); //得到所有点可以访问最远距离的最大值 cout<<ans; return 0; } #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=1e5+6; int n,s,dis[N],fa[N],flag[N],far,ans=2e9; struct edge{ int to,w; }; vector<edge> G[N]; void dfs(int u,int f){ fa[u]=f; if(dis[u]>dis[far])far=u;//记录最远的距离 for(int i=0;i<G[u].size();i++){ int v=G[u][i].to, w=G[u][i].w; if(vf||flag[v])continue; dis[v]=dis[u]+w; dfs(v,u); } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=2,u,v,w;i<=n;i++){ cin>>u>>v>>w; G[u].push_back((edge){v,w}); G[v].push_back((edge){u,w}); } int A,B; //直径的两端 dis[1]=1;dfs(1,0);A=far; //第一次dfs dis[far]=0;dfs(far,0);B=far; //第二次dfs for(int i=B,j=B; i; i=fa[i]){ while(dis[j]-dis[i]>s)j=fa[j]; //双指针法（尺取法） int x=max(dis[B]-dis[j], dis[i]); ans=min(ans,x); } for(int i=B; i; i=fa[i])flag[i]=1; //直径上的点跳过 for(int i=B; i; i=fa[i]){ dis[i]=0; dfs(i,fa[i]); //计算直径上每个点可以访问的最远距离 （可以有多条直径 } for(int i=1;i<=n;i++) ans=max(ans,dis[i]); //得到所有点可以访问最远距离的最大值 cout<<ans; return 0; }

一个线性时间复杂度的做法 找一条直径（两遍dfs），然后从一个端点开始枚举长度不超过s的另一端点（由贪心的性质显然当长度刚好小于s时比较优 ） 然后偏心距的下界大于这个端点到直径两端点的最小值 然后对于一条路径的偏心距我们发现如果去一个点要经过你的路径，这个距离显然是没有用的（因为从路径上到这个点一定有更小的距离） 所以我们就将他们无视掉

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=1e5+6; int n,s,dis[N],fa[N],flag[N],far,ans=2e9; struct edge{ int to,w; }; vector<edge> G[N]; void dfs(int u,int f){ fa[u]=f; if(dis[u]>dis[far])far=u; for(int i=0;i<G[u].size();i++){ int v=G[u][i].to, w=G[u][i].w; if(v==f||flag[v])continue; dis[v]=dis[u]+w; dfs(v,u); } } int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=2,u,v,w;i<=n;i++){ cin>>u>>v>>w; G[u].push_back((edge){v,w}); G[v].push_back((edge){u,w}); } int A,B; dis[1]=1;dfs(1,0);A=far; dis[far]=0;dfs(far,0);B=far; for(int i=B,j=B; i; i=fa[i]){ while(dis[j]-dis[i]>s)j=fa[j]; int x=max(dis[B]-dis[j], dis[i]); ans=min(ans,x); } for(int i=B; i; i=fa[i])flag[i]=1; for(int i=B; i; i=fa[i]){ dis[i]=0; dfs(i,fa[i]); } for(int i=1;i<=n;i++) ans=max(ans,dis[i]); cout<<ans; return 0; }

直接暴力dfs，时间复杂度O(n^3)