1.原题和原题链接

原题链接

B4016 树的直径

题目描述

给定一棵 $n$ 个结点的树，树没有边权。请求出树的直径是多少，即树上最长的不重复经过一个点的路径长度是多少。

输入格式

第一行输入一个正整数 $n$，表示结点个数。

第二行开始，往下一共 $n-1$ 行，每一行两个正整数 $(u,v)$，表示一条边。

输出格式

输出一行，表示树的直径是多少。

输入输出样例 #1

输入 #1

5
1 2
2 4
4 5
2 3

输出 #1

3

说明/提示

数据保证，$1\le n\le 10^5$。

2.主要思路以及AC代码

1.第一种解法及其AC代码

主要思路1

这道题求树的直径，最容易理解的方法就是使用两次dfs。核心原理很简单：先随便选一个点跑dfs，找到离它最远的节点 x；再以 x 为起点跑一次dfs，找到离 x 最远的节点 y，x 到 y 的距离就是树的直径。我们可以使用动态数组存树，dfs 记录当前的节点深度，并不断更新最大深度和对应节点。第一次 dfs 找到直径一端，第二次直接算出直径长度。2次dfs可以在同一个dfs里面完成，相较于后面的2种写法更容易理解。

AC代码1

#include<bits/stdc++.h>
using namespace std;
int n,mh=-(1<<30),x;
vector<int> g[1000005];
void dfs(int k,int fa,int h){
	if (h>mh){mh=h;x=k;}
    for(int i=0;i<g[k].size();i++){
        int v=g[k][i];
        if(v==fa) continue;
        dfs(v,k,h+1);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int k,v;cin>>k>>v;
        g[k].push_back(v);
        g[v].push_back(k);
    }
    dfs(1,0,0);mh=-(1<<30);dfs(x,0,0);cout<<mh;
    return 0;
}

2.第二种解法及其AC代码

主要思路2（1->2）

第二种是树形 dp的 解法，从两次 dfs改造而来：放弃两次遍历，只用一次dfs 遍历整棵树。上一种解法需要跑两遍dfs，这种方法在递归时，用 dp [k][0] 存节点 k 的最长子树深度，dp [k][1] 存次长子树深度。遍历每个子节点时，更新这两个值，直径就是每个节点的最长 + 次长子树深度之和。

对比优势（1->2）

只需要一次递归遍历，少一次全局搜索，且不容易出错，效率和第一种一样，但代码更精简，理解之后写起来会更快。

AC代码2

#include<bits/stdc++.h>
using namespace std;
int n,dp[100005][3],mh=0;
vector<int> g[100005];
void dfs(int k,int fa){
	dp[k][0]=dp[k][1]=0;
    for(int i=0;i<g[k].size();i++){
        int v=g[k][i];
        if(v==fa) continue;
        dfs(v,k);
        if ((dp[v][0]+1)>dp[k][0]){
        	dp[k][1]=dp[k][0];
        	dp[k][0]=dp[v][0]+1;
		}
		else if ((dp[v][0]+1)>dp[k][1]) dp[k][1]=dp[v][0]+1;
    }
    mh=max(mh,dp[k][0]+dp[k][1]);
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int k,v;cin>>k>>v;
        g[k].push_back(v);
        g[v].push_back(k);
    }
    dfs(1,0);cout<<mh;
    return 0;
}

3.第三种解法及其AC代码

主要思路3（2->3）

第三种同解法2一样是树形 dp，但是第二种双层数组写法的极致简化：把 dp [k][0] 和 dp [k][1] 合并成单个 dp 数组。遍历子节点时，先用当前 dp [k]（还未更新的最长深度）+dp [v]+1 更新直径，再更新 dp [k] 为最大深度，直接用一个变量完成两种深度的计算。

对比优势（2->3）

代码量最少，空间占用更小，计算步骤也更少，运行效率依旧和前两种一致，但考场写这个速度最快，是这3种解法里面最优的。（当然还是比较推荐解法1的，毕竟最容易理解）

AC代码3

#include<bits/stdc++.h>
using namespace std;
int n,dp[100005],mh=0;
vector<int> g[100005];
void dfs(int k,int fa){
	dp[k]=0;
    for(int i=0;i<g[k].size();i++){
        int v=g[k][i];
        if(v==fa) continue;
        dfs(v,k);
        mh=max(mh,dp[k]+dp[v]+1);  
		dp[k]=max(dp[k],dp[v]+1);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int k,v;cin>>k>>v;
        g[k].push_back(v);
        g[v].push_back(k);
    }
    dfs(1,0);cout<<mh;
    return 0;
}

以上就是本篇全部内容，感谢浏览！