http://www.lydsy.com/JudgeOnline/problem.php?id=1509
要从一棵树中找出三个点 X,Y,Z ，使得 min(dis[A][C],dis[B][C])+dis[A][B] 最大，求这个最大值
可以发现，min里头的两个东西具体取哪个并不重要，或者说点C距离A更近还是距离B更近并不重要。下面给出一个结论： min(dis[A][C],dis[B][C])+dis[A][B] 取最大值时，路径AB是整个树的直径(最长链)，通过BFS找出树的直径后，直接枚举点C即可得到最大答案。
不过复习此题主要还是为了复习树的直径的求法。可以通过两次BFS求出树的直径AB（树上最长链AB）：
第一次BFS：任意选择一个起点，搜出距离这个点最远的点A，也就是最长链的一个端点。
第二次BFS：选择A作为起点，搜出距离这个点最远的点B，也就是最长链的另一个端点。
第二次BFS的正确性是显然的，因为如果我们已经知道了最长链的一个端点，就能很容易地通过求最长路来求出最长链的另外一个端点。
下面证明第一次BFS的正确性。
Case 1.第一次BFS选择的起点在最长链上。此时假如得到的最远点A不是最长链端点，那么显然就会存在A‘，A’到起点距离比A到起点距离更远，然而BFS找出的是距离起点最远的点，与之前矛盾，证毕。
Case 2.第一次BFS选择的起点不在最长链上，且此时起点到A的路径和最长链相交，设交点为x，则x到A的路径必然是最长链的后半段。假如不是的话，就能存在A’(A’就是最长链的端点),使得x到A‘距离比x到A距离更远，最长链的后半段也因此是xA’而不是xA，同样地，A‘比A距离起点更远，这是显然的。但是由于BFS找出的是距离起点最远的点，与之前矛盾，故不存在这样的A‘，xA就是最长链的后半段，证毕。
Case 2.第一次BFS选择的起点不在最长链上，且此时起点到A的路径和最长链不相交
显然最长链的长度应该比起点到A长度更长，若相等的话，起点到A的链就同样是最长链了。
考虑上图。由于是树，所以起点到A的链和最长链端点之间必然存在一条如图所示的红色路径。
显然X-A长度比X-5长度短，因为X-5是最长链。因此2-A长度比2-5长度短。1-A长度(2-A长度-1)比1-5长度短(2-5长度+1)，也就是说A比5距离起点更近。而BFS找出的是离起点最远的点，与之前矛盾，故不存在Case 3。证毕。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 210000
using namespace std;
typedef long long int LL;
struct edge
{
int u,v,w,next;
}edges[MAXN*2];
int head[MAXN],nCount=0;
void AddEdge(int U,int V,int W)
{
edges[++nCount].u=U;
edges[nCount].v=V;
edges[nCount].w=W;
edges[nCount].next=head[U];
head[U]=nCount;
}
int n,m;
bool vis[MAXN];
int q[MAXN];
int BFS(int S,LL dist[]) //求出每个点到S的距离，保存在dist[]里，并返回距离S最远的点
{
memset(vis,false,sizeof(vis));
int h=0,t=1;
q[h]=S;
dist[S]=0;
vis[S]=true;
int farthest=0; //最远点
while(h<t)
{
int u=q[h++];
for(int p=head[u];p!=-1;p=edges[p].next)
{
int v=edges[p].v;
if(vis[v]) continue;
vis[v]=true;
dist[v]=dist[u]+edges[p].w;
q[t++]=v;
vis[v]=true;
if(dist[v]>dist[farthest]) farthest=v;
}
}
return farthest;
}
LL dista[MAXN],distb[MAXN];
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
AddEdge(u,v,w);
AddEdge(v,u,w);
}
int a=BFS(1,dista);
int b=BFS(a,dista);
BFS(b,distb);
LL ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,min(dista[i],distb[i]));
printf("%lld\n",ans+dista[b]);
return 0;
}