其实本题最难的部分不是从 \(O(n^3)\) 暴力优化到 \(O(n)\) 的那些东西（本来暴力就可以过题，我做的时候只打了暴力），而是“只需要考虑一条直径”这一部分，这题对树的直径相关概念的要求才是重点。
引理1：树中任何两条直径相交
证明：考虑两个直径 \(AB,CD\)，如果 \(AB,CD\) 不相交，则我们可以把这两条直径连起来形成更长的直径，矛盾。
引理2：树中任何两条直径相交后不会再相交
证明：这是由树的性质得到的推论，设第一次相交后的最后一个点为 \(X\)，第二次相交的第一个点为 \(Y\)，则有两条不同的 \(XY\)，与树的性质矛盾。
引理3：树的所有直径交于一处
证明：这是由引理1与引理2的推论，假设有 \(3\) 条不同直径 \(l_1,l_2,l_3\)， \(l_1,l_2\) 交于 \(A\)，\(l_1,l_3\) 交于 \(B\)，\(l_2,l_3\) 交于 \(C\)，假设 \(A,B,C\) 三个点全部不重合，那么 \(A,B,C\) 三点成环；假设 \(A,B\) 重合，和 \(C\) 不重合，只要在草稿纸上画一下我们就会发现这是不存在的，此时 \(C\) 也和 \(A,B\) 重合。由 \(3\) 条直线重合在一处可以推广得到任意直径都会重合在一处。
但是要注意的是这里的“一处”不一定是一个点。想像一颗树，主干是一条边 \(u<->v\)，\(u\) 又接了 \(3\) 个点，\(v\) 也接了 \(3\) 个点，此时这棵树的直径有 \(3\times 3=9\) 条，但是它们都有公共部分：边 \(u<->v\)，它并不是一个点。不过“相交部分”一定会包含一个点进去，为了方便讨论，下文我们把所有直径的“相交部分”缩成一个点。
引理4：两条直径关于交点所分成的上下两部分长度相等
证明：这是由“树的直径”的定义得出的。假设直径 \(AB,CD\) 交于 \(E\)，引理的意思是 \(AE,BE,CE,DE\) 四段长度完全相等。先证 \(AE=CE\)，假设 \(AE>CE\)，那么 \(CE+DE<DE+AE\)，而 \(CE+DE=CD\) 又是树的直径，矛盾；\(AE<CE\) 时同理。根据 \(AE=CE\) 的证明方法我们还能得到下半部分相等，即 \(BE=DE\)。此时只需要证 \(AE=BE\)，假设 \(AE<BE\)，由刚才的证明我们得到 \(AE=CE<BE=DE\)，那么 \(BE+DE>BE+AE\)，但是 \(BE+AE=AB\) 又是树的直径，矛盾；\(AE>BE\) 时同理，综上 \(AE=CE,BE=DE,AE=BE\)，所以我们已经证明了 \(AE=BE=CE=DE\)。
好现在再来思考为什么只需要考虑一条直径，假设有多条直径，由引理 \(3\)，它们都会交于一处 \(E\)，此时考虑其中一条直径 \(AB\)，由引理 \(4\),\(AE=BE\)，那么此时我们在直径 \(AB\) 上选择“树网的核”，一定是优先选择这个 \(E\) 的。这个道理很简单，如果给一条直线 \(AB\)，让你选个 \(C\)，使得 \(\max(|A-C|,|B-C|)\) 最短你会选哪个点？中点！而 \(E\) 就是中点。而一旦你选择了这个中点，其实不管你怎么拓展，偏心距其实已经定下来了。(这点并不难证明，由前4个引理加上一个显然的事实“直径上一点的最远点一定是该条直径的两个端点之一”可以轻松推导出来”）所以不管你选哪一条直径做，都是一样的。
确定了这点我想怎么乱搞大家都会了吧（实际上就算我们发现不了只需要考虑一条直径，由于一个点只会作为一条直径的起点，最多只有 \(n\) 个直径，对这 \(n\) 条直径暴力枚举核，然后暴力找最远点复杂度也不过是 \(O(n^4)\)，原题中足以拿到70分的好分数）
这题还没有要写高精的第三题难？？
这题放在NOIP 2020也就T2的难度吧（雾）
\(O(n^3)\) 的暴力代码：
//NOIp2007，提高T4
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=350,MAXM=650,INF=1e9+10;
int n,s;
int dis[MAXN][MAXN],ans=INF;
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j)dis[i][j]=INF;
}
}
for(int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=dis[v][u]=w;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
//找出一条直径即可
int st,ed,len=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>len){
len=dis[i][j];
st=i;ed=j;
}
}
}
for(int i=1;i<=n;i++){
if(dis[st][i]+dis[i][ed] != dis[st][ed])continue;
for(int j=1;j<=n;j++){
if(dis[st][j]+dis[j][ed] != dis[st][ed])continue;
if(dis[i][j]>s)continue;
int ecc=-INF;
for(int k=1;k<=n;k++){
ecc=max(ecc,(dis[i][k]+dis[j][k]-dis[i][j])/2);
}
ans=min(ans,ecc);
}
}
printf("%d",ans);
return 0;
}
水印：Cry_For_theMoon（不过没人会看我这种垃圾OIer的博客吧qwq）