树的最长链

在做搜索题或者树的相关题目时，经常会遇到求树的最长链问题，本文主要涉及以下内容：
1.求树的最长链的方法
2.对该方法的证明
3.举一个相关题目为例
一、方法
正如文章开头所写，求树的最长链的方法就是搜索。准确的说，是用两次搜索。
第一次，随便找树上的一个节点T，通过一次搜索找到距离该点最远的一个点A
第二次，通过一次搜索，找到距离A最远的一个点B，则dis(AB)即为树的最长链

二、证明
求解方法很简单，使用起来也是完全正确的。但是想要知其所以然，就要完备的证明。证明分为两种情况，如下：
1.T刚好为最长链上的一个点

T为最长链上的点.png

这种情况下，找到的点A一定是最长链的一个端点。由于T是最长链上的点，那么最长链的另一个端点到T的距离是一定的，因此A到T必定要取最长的距离，该链才能最长。此种情况容易理解，不加赘述。
2.T不在最长链上

T不在最长链上.png
该情况较为抽象，难理解，希望读者拿出纸笔，边看边画，加快和加深理解。
若T不在最长链上，则最长链必定在T的一个子树中。上图中最长链就在以C为根的子树中。
那么我们可以下一个结论一：找到距离T最远的一个点A，那么A必定是最长链的一个端点，且从A到T的路径必定与最长链重合从A到C的这一段。
下面我们来证明结论一：
假设T的最长链在子树C中，且子树C中最深的节点A对于根节点T的深度为h(A)。如果距离T最远的某个节点P不在子树C中，那么P-T-C-A的长度一定大于子树C中最长链的长度，与T中最长链在子树C中的条件矛盾。所以A必为最长链的一个端点，然后再一次搜索找到距离A最远的节点B，AB即为最长链。

三、例子
https://vijos.org/p/1107
这是vijos总域中的一道题。题目是有不少小坑的，必须仔细读题和思考才能想到这是一道求树的最长链的问题。通过题目中“假设任意的两个风景点都有且仅有一条路径（无回路）相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。”这句话，可以看出这个图是一个连通无环图，也即一棵树。而必须找到最长的一条路径，即为求树的最长链。
我的AC代码如下：

#include<iostream>
#include<queue>
using namespace std;
int col,row;
int gra[1005][1005];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool judge(int i,int j);
const int IM=(1<<30);
struct Node
{
    int x,y;
}; 
Node head;//最长链的一个端点
Node tail;//最长链的另一个端点
void bfs(int,int,int);
int main()
{
    ios::sync_with_stdio(false);
    cin>>col>>row;
    Node init;//随意找一个点作为初始点
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            char c;
            cin>>c;
            if(c=='#')
                gra[i][j]=0;
            else
            {
                gra[i][j]=1; 
                init.x=i;init.y=j;
            }
        }
    }
    bfs(init.x,init.y,1);//一次广搜找到最长链的一个端点head
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            if(gra[i][j]!=0)
                gra[i][j]=1;
        }
    }
    gra[head.x][head.y]=2;//第二次广搜找到最长链的另一个端点tail
    bfs(head.x,head.y,2);
    cout<<gra[tail.x][tail.y]-gra[head.x][head.y]<<endl;
    return 0;
} 
bool judge(int i,int j)
{
    return i>=0&&i<row&&j>=0&&j<col;
}
void bfs(int x,int y,int cnt)
{
    Node t;
    t.x=x;t.y=y;
    queue<Node> q;
    q.push(t);
    while(!q.empty())
    {
        Node temp=q.front();
        q.pop();
        if(cnt==1)  head=temp;
        else    tail=temp;
        for(int k=0;k<4;k++)
        {
            if(judge(temp.x+dx[k],temp.y+dy[k])&&gra[temp.x+dx[k]][temp.y+dy[k]]==1)
            {
                Node next;
                next.x=temp.x+dx[k];next.y=temp.y+dy[k];
                gra[next.x][next.y]=gra[temp.x][temp.y]+1;
                q.push(next);
            }
        }
    }
}