[NOI 2015复习][BZOJ 1509][NOI 2003]逃学的小孩(树的直径)

题目链接

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;
}