题意简化
给定一棵带边权无根树,在其直径上求出一段长度不超过s的路径F,使得离路径距离最远的点到路径的距离最短。
传送门
题解
不难发现,对于直径上的任意一点,距离它最远的点一定是直径的某一端点
所以我们不妨把这句话拓展一下
即
对于任意一点距离它最远的点一定在直径上
所以找直径的话,就是先随便找个点找到离他最远的点
这个点一定在直径上
然后再从这个点出发就能找到了直径的端点
然后直接尺取法
再把直径上的每个点都找一下最远的点就好
代码
#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define in inline
#define get getchar()
in int read()
{
int t=0; char ch=get;
while(ch<'0' || ch>'9') ch=get;
while(ch<='9' && ch>='0') t=t*10+ch-'0',ch=get;
return t;
}
const int _=1001;
int k,h[_],top,n,m,f[_],dis[_],vis[_],tot,ans=2e9;
struct edge{
int to,ne,w;
}e[_];
in void add(int x,int y,int z)
{
e[++tot].to=y,e[tot].ne=h[x],e[tot].w=z,h[x]=tot;
}
in void dfs(int x,int fa)
{
// cout<<x<<endl;
f[x]=fa;
if(dis[x]>dis[k])k=x;
for(re int i=h[x];i;i=e[i].ne)
{
int y=e[i].to;
if(y==fa||vis[y])continue;
dis[y]=dis[x]+e[i].w;
dfs(y,x);
}
}
int main()
{
n=read(),m=read();
for(re int i=1;i<n;i++)
{
int z=read(),y=read(),l=read();
add(z,y,l);
add(y,z,l);
}
dis[1]=1;dfs(1,0);
dis[k]=0;dfs(k,0);
top=k;
int x;
for(re int i=top,j=top;i;i=f[i])
{
while(dis[j]-dis[i]>m)j=f[j];
x=max(dis[top]-dis[j],dis[i]);
ans=min(ans,x);
}
for(re int i=top;i;i=f[i])vis[i]=1;
for(re int i=top;i;i=f[i])
{
k=i,dis[k]=0;
dfs(i,f[i]);
}
for(re int i=1;i<=n;i++)
ans=max(ans,dis[i]);
cout<<ans<<endl;
}