好久没写题解了。这题不算太水就写一下题解。
话说回来，虽然不水但是挺裸。可以说题意即一半题解了。
我猜粘了题面也没有人去看的，所以直接人话题意了。
给一棵树，点数1e6，(当年noip的n当然是只有300了，，)，就管他叫树网。
首先定义树的直径：树上最远点对之间的路径。我们定义树的一个点到一段路径的距离是：点和路径上最近的点之间路径长。
然后定义一段路径的偏心距ecc：除了这这路径上的点，其他点到这条路径的距离中的max。（和所有点没区别）
现在要求出这样一个路径，它在一条直径上（直径可能不止一个），它的长度不超过一个给定的值lim，满足前两个条件的情况下偏心距最小。我们叫他树网的核。（终于扣题了woc）
所以我们需要知道一些事情。
1，树的直径可能不止一个，但不论用哪个直径所能求出的该最小偏心距相等。
2，离一个点最远的点一定是一条直径的一端。
虽然我不知道为啥。。但我觉得很有道理啊对不对。。。
于是在这基础上思路就很明显。
先根据性质2求出一条直径。然后显然是不超过lim情况下这一段越长越好。于是枚举结束点，开始点随之后移（就是双指针啥的扫一遍）。
对于一条路径其偏心距有两种情况：
1，开始点或结束点与所在直径上离得近的那个端点的距离。
2，不经过所在直径的情况下，能到达的其他点中与它距离最远的距离。
仔细想想(YY)一下就知道，不理解，，，私吧。
情况2与起始点结束点无关，可以预处理f(x)，复杂度是O(n)的，因为一个点只会被遍历一次。
于是情况2变成了单调队列问题：求区间最大值，，不是定长区间了，deque的pop_front条件变为了q.front()与当前枚举的结束点距离<lim。
要注意的是q.front()并不是起始点，而是起始点到结束点中f(x)最大的。（好像只有我这么想脑残wa了一发）起始点是贪心选的，因为越长越好，只要不超过lim就好。
貌似没有什么细节问题了，dfs还是巨好写的。附代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
inline int read(){
int r=,c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))
r=r*+c-'',c=getchar();
return r;
}
struct Edge{
int to,nxt,w;
}e[N*];
int head[N],cnt=;
void add(int u,int v,int w){
e[cnt]=(Edge){v,head[u],w};
head[u]=cnt++;
e[cnt]=(Edge){u,head[v],w};
head[v]=cnt++;
}
int n,lim,mx;
int S,T,d[N];
bool ind[N];
void dfs(int u,int fa){
mx=max(mx,d[u]);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa||ind[v])continue;
d[v]=d[u]+e[i].w;
dfs(v,u);
}
}
int nxt[N],dis[N];
void dfs2(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs2(v,u);
if(ind[v])
nxt[u]=v,dis[u]=e[i].w,ind[u]=;
}
}
void init(){
n=read(),lim=read();
for(int i=;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w);
}
}
void diameter(){
mx=;dfs(,);
for(int i=;i<=n;i++)
if(d[i]==mx)S=i;
memset(d,,sizeof d);
mx=;dfs(S,);
for(int i=;i<=n;i++)
if(d[i]==mx)T=i;
}
int l[N],f[N];
void get(){
ind[T]=;dfs2(S,);
int t=;
for(int u=S;u;u=nxt[u]){
d[u]=mx=;l[u]=t;
t+=dis[u];
dfs(u,);f[u]=mx;
}
}
void solve(){
deque<int>q;
q.push_back(S);
int ans=2e9,h=S;
for(int u=S;u;u=nxt[u]){
int m=f[u];
while(!q.empty()&&f[q.back()]<m)
q.pop_back();
q.push_back(u);
while(l[u]-l[q.front()]>lim)
q.pop_front();
int v=q.front();
while(l[u]-l[h]>lim)h=nxt[h];
ans=min(ans,max(f[v],max(l[h],l[T]-l[u])));
}
printf("%d\n",ans);
}
int main(){
init();
diameter();
get();
solve();
}
欢迎dalaoD我，鄙视dalao装弱%我。。。