树的直径

定义

    一棵树中最长的简单路径，简单路径是指两点间只被访问一次.
    通俗来讲，就是树上的 最长链的长度.

解一：两次DFS遍历

  首先，对任意结点(默认为节点1)开始进行第一次DFS，到达距离最远的点一定是直径的一个端点；再次从该端点开始DFS，第二次到达的最远的点必为直径的另一个端点,故两点之间的距离就是树的直径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
int n, c;
vector<vector<int>> e(n + 1);
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    vector<int> dis(n + 1);
    for (int i = 1; i < n;i++){
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u); //邻接表存图
    }
    auto dfs = [&](auto dfs, int u, int fa) -> void
    {
        for (auto it : e[u]){
            if (it == fa)
                continue;
            dis[it] = dis[u] + 1;
            if(dis[it]>dis[c])
                c = it; //更新最远点
            dfs(dfs, it, u);
        }
    };
    dfs(dfs, 1, 0); //第一次dfs找最远端点
    dis[c] = 0;
    dfs(dfs, c, 0); //第二次dfs找另一端点
    cout << dis[c] << endl;
    return 0;
}

    此外，该方法还可以在第二次DFS时记录树的直径的各点

切记，两次DFS法只能用于树的边权非负！！！

解法二：树形DP