传送门1 noip版
传送门2 加强版
当年(O(n^3))算法即可过
但是AC不是我们的做题的唯一目标，
我们做题应是为了取得经验。
于是我们直接讨论(O(n))算法
题意：
其实这道题我们完全不需要知道树网的核是什么东西
简单讲，就是在直径上取一条长度 < S 的路径
使最远的点到这条路径的距离最小
求这个最小值
解法：
显然要先求出直径
并记录这条路径（可用前驱节点）
多条直径也无妨 取一条即可
对于直径上每个点，求不过直径上的点到该点距离最大值 记作len
通过dfs求直径必定会求到直径上的点到起点的距离，这样就可以计算直径上两点的距离了
因为两点距离越大越好
则可以用尺取法求到直径上任意满足距离 < S 的两点 记作i,j（其中i靠近起点sp，j靠近终点ep）
又因为直径的性质 根据题意易得
这两点确定时答案即为 max(dist(i,sp)，dist(j,ep)，len）
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define inf 2147483647
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
#define dist(i,j) abs(d[i]-d[j])
using namespace std;
typedef long long ll;
int n,s;
int ds[500010],minn=inf,len;
int ans=0,sum=0,sp,ep,d[500010];
int tot=1,head[500010],fa[500010];
bool v[500010];
struct EDGE
{
int to,d,nxt;
}edge[1000010];
void add(int u,int v,int d)
{
edge[++tot].d=d;
edge[tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}
int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x;
}
void dfs(int x)
{
v[x]=1;
if(ans<d[x])
{
ans=d[x];
ep=x;
}
for(int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if(v[y]) continue;
d[y]=d[x]+edge[i].d;
fa[y]=x;
dfs(y);
}
v[x]=0;
}
void get_d(int x)
{
v[x]=1;
len=max(len,ds[x]);
for(int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if(v[y]) continue;
ds[y]=ds[x]+edge[i].d;
get_d(y);
}
v[x]=0;
}
int main()
{
n=read(),s=read();
rep(i,1,n-1)
{
int u=read(),v=read(),d=read();
add(u,v,d),add(v,u,d);
}
dfs(1);
sp=ep,ans=0,d[ep]=0;
dfs(sp);
fa[sp]=sp;
for(int i=ep;;i=fa[i])
{
v[i]=1;
if(i==fa[i]) break;
}
for(int i=ep;;i=fa[i])
{
ds[i]=0;
get_d(i);
v[i]=1;
if(i==fa[i]) break;
}
int i=ep,j=ep;
for(;;i=fa[i])
{
while(dist(i,j)>s)
{
j=fa[j];
}
minn=min(minn,max(dist(i,sp),dist(j,ep)));
if(i==fa[i]) break;
}
printf("%d
",max(minn,len));
return 0;
}