（bzoj数据加强）
前置知识：树的直径
（并不想贴我的智障写法虽然快1倍但内存占用极大甚至在bzoj上MLE）
正常写法之一：用常规方法找到树的直径，在直径上用尺取法找一遍，再dfs，再全图找一遍。
分类讨论：
1.偏心距可能是所取路径上（非端点）的某一点与直径外一点的距离
解决方案：在该点上跑一遍dfs，不能通过树的直径，找到距离最远的点。
2.偏心距可能是所取路径的端点与直径端点之间未取部分的长度。
所取路径的端点在直径上，根据性质，与它相对距离最远的点十分显然是直径的端点。
解决方案：在直径上用尺取法找一遍
end.
#include<iostream> #include<cstdio> #include<cstring> #define rint register int using namespace std; void read(int &x){ char c=getchar();x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar(); } #define N 500002 int n,s,k,ans=1e9,fa[N],mark[N],d[N]; int cnt,hd[N],nxt[N<<1],ed[N],poi[N<<1],val[N<<1]; inline void adde(int x,int y,int v){ nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt, ed[x]=cnt, poi[cnt]=y, val[cnt]=v; } void dfs(int x,int ffa){ fa[x]=ffa; if(d[x]>d[k]) k=x; //更新距离最远的点 for(int i=hd[x];i;i=nxt[i]){ int to=poi[i]; if(to==ffa||mark[to]) continue; d[to]=d[x]+val[i]; dfs(to,x); } } int main(){ read(n); read(s); int q1,q2,q3; for(rint i=1;i<n;++i){ read(q1); read(q2); read(q3); adde(q1,q2,q3),adde(q2,q1,q3); }k=1; dfs(1,0); d[k]=0; dfs(k,0);//常规方法求树的直径 for(rint i=k,j=k;i;i=fa[i]){ while(d[j]-d[i]>s) j=fa[j]; ans=min(ans,max(d[k]-d[j],d[i])); }//在直径上用尺取法找偏心距 for(rint i=k;i;i=fa[i]) mark[i]=1; for(rint i=k;i;i=fa[i]) d[i]=0,dfs(i,fa[i]);//dfs找路径上某点与非直径的某点的偏心距 for(rint i=1;i<=n;++i) ans=max(ans,d[i]);//全图找一遍 printf("%d",ans); return 0; }