定义：

树的直径，即 树上最远的两点的距离（即 树上最大距离），若树的边权全为$1$，则树的直径即是 树上的最长链。

通常有两种树的直径的求法，时间复杂度均为$O(n)$

①树形DP求树的直径

改方法只需遍历一次，即可求得树的直径大小，但无法求得直径的具体路径。

选取任意结点为根遍历树，设 $d[i]:$表示结点$i$为根的子树结点最远距离。

则有：

• $u$为根的子树结点最远距离 d [ u ] = max ? { d [ v ] + w u ? v }        v ∈ u d[u]=\max\{d[v]+w_{u-v}\}\;\;\;v\in u d[u]=max{d[v]+wu?v?}v∈u的子结点

最后直径即为 根结点 的 两个最远距离之和

int d[maxn],len=0;
void DP(int u,int pre)
{
    d[u]=0;   //初始为0
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(v==pre)
            continue;
        DP(v,u);
        len=max(len,d[u]+d[v]+w);  //更新直径
        d[u]=max(d[u],d[v]+w);
    }
}

int dist[maxn],s,max_dist;
void DFS(int u,int pre)
{
    if(dist[u]>max_dist)
    {
        max_dist=dist[u];
        s=u;
    }
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(v==pre)
            continue;
        dist[v]=dist[u]+w;
        DFS(v,u);
    }
}
int get_len()
{
    max_dist=dist[1]=0;
    s=1;
    DFS(1,-1);
    max_dist=dist[s]=0;
    DFS(s,-1);
    return max_dist;
}