题意：给一棵无根树，要求一个有长度限制的路径使得 距离这条路径最远的点 距此路径的距离最小
性质：对一个点，距离它最远的点是直径上两个端点之一，不然不要原来的端点把那个更远的点连到直径上直径会更长
对直径上的一条路径，如果某 不在直径上的点b 到此路径上最近的点 是这条路径的端点a，那么这个距离一定小于 a到距a最远的直径端点，
如果b到此路径上最近的点不是路径端点而是路径内点c，那么这个点b就需要被考虑进答案中了，因为c虽然到直径某端点很远但是因为它不是路径的端点，所以实际上这个路径距离直径的某端点会稍短一些，这样点b就有可能更新答案，例：（d为直径一端点
所以我们把直径看做一个序列，每个点都有一个权值即距它最远的点的距离，现在要在序列上取不大于s的一段使最大权值最小，我们可以在直径上尺取，用单调队列维护最大值，注意还要处理路径端点到直径端点
然而其实不用单调队列，直接对所有点的权值取max即可，原因在于如果某点不在尺取范围内，那么它一定不如到直径的端点长（上面已证，如果答案取上这个点那么我们取max更新了很对，如果没取上那么一定有其他大于它的，对答案没有影响
#include<bits/stdc++.h> using namespace std; const int maxn=309; int n; struct node{ int v,nxt,w; }e[maxn<<1]; int head[maxn],cnt; inline void add(int u,int v,int w){ e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt; } int dis[maxn],far,from[maxn],fa[maxn]; void pre(int x,int f){ fa[x]=f; for(int i=head[x];i;i=e[i].nxt){ if(e[i].v==f||dia[e[i].v])continue; dis[e[i].v]=dis[x]+e[i].w; dfs(e[i].v,x); } if(dis[x]>dis[far])far=x; } int ans=1e9; bool dia[maxn]; int main(){ scanf("%d",&n); for(int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } dis[1]=0;pre(1,0); dis[far]=0;pre(far,0); int top=far; for(int i=top,j=top;i;i=fa[i]){ while(dis[j]-dis[i]>m)j=fa[j];//尺取 x=max(dis[top]-dis[j],dis[i]);//路径端点到直径端点的最小贡献 ans=min(ans,x); } for(int i=top;i;i=fa[i])dia[i]=1;//标记直径 for(int i=top;i;i=fa[i]){ far=i;dis[far]=0; pre(i,fa[i]);//计算每个点权值 } for(int i=1;i<=n;i++)ans=max(ans,dis[i]); printf("%d",ans); }