要求最大值最小容易想到二分答案。首先对每个点求出子树中与其最远的距离是多少，二分答案后就可以标记上一些必须在所选择路径中的点，并且这些点是不应存在祖先关系的。那么如果剩下的点数量>=3，显然该答案不可行；=0，显然可行；=1，由该点沿其到根的路径往上爬，并计算最远距离判断是否合法；=2，求出两点lca后与1的做法类似。
noip原题是要求该路径在一条直径上，事实上这条最优路径一定是在直径上的，不过并不太懂这之间的关系。
写的太丑于是常数巨大，bzoj上愉快的T掉了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 500010 int n,m,p[N],deep[N],up[N],f[N],fa[N],t=0,ans=0,cnt,q[4]; struct data{int to,nxt,len; }edge[N<<1]; void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} void dfs(int k) { for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { fa[edge[i].to]=k; deep[edge[i].to]=deep[k]+1; up[edge[i].to]=edge[i].len; dfs(edge[i].to); f[k]=max(f[k],f[edge[i].to]+edge[i].len); } } void paint(int k,int x) { if (cnt>2) return; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { paint(edge[i].to,x); if (cnt>2) break; if (f[edge[i].to]+edge[i].len>x&&f[edge[i].to]<=x) q[++cnt]=edge[i].to; if (cnt>2) break; } } bool check(int k) { cnt=0; paint(1,k); if (cnt>2) return 0; if (cnt==2) { int x=q[1],y=q[2],len=0; while (x!=y) { if (deep[x]<deep[y]) swap(x,y); len+=up[x],x=fa[x]; } if (len>m) return 0; len=0; while (fa[x]) { y=x,len+=up[x],x=fa[x]; if (len>k) return 0; for (int i=p[x];i;i=edge[i].nxt) if (edge[i].to!=y&&edge[i].to!=fa[x]&&f[edge[i].to]+edge[i].len+len>k) return 0; } } if (cnt==1) { int x=q[1],y,len=0,flag=0; while (fa[x]) { y=x,len+=up[x],x=fa[x]; if (!flag&&len>m) flag=1,len=up[y]; if (len*flag>k) return 0; for (int i=p[x];i;i=edge[i].nxt) if (edge[i].to!=y&&edge[i].to!=fa[x]&&f[edge[i].to]+edge[i].len+len*flag>k) return 0; } } return 1; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj2282.in","r",stdin); freopen("bzoj2282.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(),m=read(); int l=0,r=0; for (int i=1;i<n;i++) { int x=read(),y=read(),z=read();r+=z; addedge(x,y,z),addedge(y,x,z); } dfs(1); while (l<=r) { int mid=l+r>>1; if (check(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<<ans; return 0; }