【传送门：BZOJ1509】
简要题意：
给你一棵有n个点树
找出三个点x,y,z
求从一个点x出发，先到另外两个点中距离x较近的点，再到剩下的那个点的时间
题解：
我们不妨先假设从x出发，先到y，再到z，这样子的话我们所花费的时间就是dis(x,y)+dis(y,z)
很显然我们肯定要让dis(y,z)尽可能的大，并且保证dis(x,y)<dis(x,z)
这样子我们先找出树的直径（任意从一个点找出离它最远的点t，再从t找出它最远的点tt，然后dis(t,tt)就是树的直径）
那么这个直径就是dis(y,z)
然后我们找出t和tt到所有点的距离，然后找出min(dis(t,i),dis(tt,i))中的最大值就好了
注意要用long long
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; struct node { int x,y,next;LL d; }a[410000];int len,last[210000]; void ins(int x,int y,LL d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } LL far;int t; void findfar(int x,int fa,LL d) { if(d>far) far=d,t=x; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fa) findfar(y,x,d+a[k].d); } } bool bk; LL d1[210000],d2[210000]; void findd(int x,int fa,int t) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fa) { if(t==1) d1[y]=d1[x]+a[k].d; else d2[y]=d2[x]+a[k].d; findd(y,x,t); } } } int main() { int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int x,y;LL d; scanf("%d%d%lld",&x,&y,&d); ins(x,y,d);ins(y,x,d); } far=0;findfar(1,0,0); int t1=t; far=0;findfar(t1,0,0); int t2=t; findd(t1,0,1); findd(t2,0,2); LL ans=0; for(int i=1;i<=n;i++) ans=max(ans,min(d1[i],d2[i])); printf("%lld ",ans+far); return 0; }