求一棵树的直径的长度模板题

主要介绍两种方法，一种是进行两次dfs进行求解，我们先任选一个点，然后对这个点进行dfs求出离这个点最远的那个点，我们记为p，然后，我们再以p为起点，进行dfs求出离p点最远的那个点，我们记为q，pq长度就是我们要求的这颗树的直径了。

代码：

#include<iostream> 
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100010;
int head[N],nxt[N],ver[N],edge[N];
int n,m,p,tot,ans;
int d[N];
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z;
    nxt[tot]=head[x],head[x]=tot;
}
void dfs(int u,int fa){
    if(ans<d[u]){ 
    /*在这之前我们就已经得知了u这个点离起点的长度了，然后。
    我们可以更新ans，同时记录可能的终点*/ 
        ans=d[u];
        p=u;
    }
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(v==fa)  continue;
        d[v]=d[u]+edge[i];
        dfs(v,u);
    }
}
void Find(int x){
    d[x]=0,ans=0;
    dfs(x,0);
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    Find(1);
    Find(p);
    cout<<ans<<endl;
    return 0;
}

第二种做法是利用dp来进行处理，我们假设d[i]表示的是以i为根结点的所有子树结点中离i最远距离。然后再dp到每个结点的时候我们可以处理简介求树上最长的子链的长度。

代码：

#include<iostream> 
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100010;
int head[N],nxt[N],ver[N],edge[N];
int n,m,p,tot,ans;
int d[N];
bool v[N];
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z;
    nxt[tot]=head[x],head[x]=tot;
}
void dp(int x){
    memset(d,0,sizeof(d));
    v[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i],w=edge[i];
        if(v[y])  continue;
        dp(y);
        ans=max(ans,d[x]+d[y]+w);
/*在这里更新答案，我们这里的两个d确保了在y结点的两端，也就是这里出现的就是
我们要求的最长链*/
        d[x]=max(d[x],d[y]+w);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    dp(1);
    cout<<ans<<endl;
    return 0;
}