求树的直径的三种方式

模板题传送门

求树的直径一共有三种方式：

1. 树形dp求树的直径
2. dfs求树的直径
3. 两次bfs/dfs求树的直径

方法 $1, 2$ 适用面较广，可以求带有负权值的树的直径的长度。
方法 $3$ 比较局限，只能求权值非负的树的直径的长度，但同时还可以求出具体路径

树形dp求树的直径

/*
设 1 号点为根节点，这样无根树就变成有根树。

设 d[x] 表示从节点 x 出发走向以 x 为根的子树，能够到达的最远节点的距离。
设 x 的子节点为 y[1], y[2], ..., y[t]，w(x, y) 表示边权，则：d[x] = max(d[y[i]] + w(x, y[i])) (1 <= i <= t)

然后考虑对每个节点 x 求出经过节点 x 的最长链的长度 f[x]，整棵树的直径就是 max(f[x]) (1 <= x <= n)

对于 x 的任意两个节点 y[i] 和 y[j]，经过节点 x 的最长链的长度可以通过四个部分构成：从 y[i] 到 y[i] 子树中的最远距离，
w(x, y[i])，w(x, y[j])，从 y[j] 到 y[j] 子树中的最远距离。若假设 j < i，则：

    f[x] = max(d[y[i]] + w(x, y[i]) + d[y[j]] + w(x, y[j])) (1 <= j < i <= t)

照以上思路即可求解本题，但是没必要使用两层循环来枚举 i, j，可以思考 d[x] 的过程，在枚举节点 x 的子节点时，
当枚举到节点 i 时，d[x] 恰好就保存了从节点 x 出发走向以 y[j](j < i) 为根的子树，能够到达的最远节点的距离，
这个距离就是 max(d[y[j]] + w(x, y[j])) (1 <= j < i)，所以此时我们可以先用 d[x] + d[y[i]] + w(x, y[i]) 更新
f[x]，再用 d[y[i]] + w(x, y[i]) 更新 d[x] 即可。
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = N * 2;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d[N]; //d[i] 表示从节点 i 出发走向以节点 i 为根的子树，能够到达的最远节点的距离
int res; //记录树的直径

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dp(int u, int father) //树形dp
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue; //不往父节点走导致死循环

        dp(j, u); //先dp子节点
        res = max(res, d[u] + d[j] + w[i]); //更新树的直径
        d[u] = max(d[u], d[j] + w[i]); //更新从 u 走向以 u 为根的子树能走到的最远距离
    }
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c); //无向图
    }

    dp(1, -1); //从任意一点为根节点往下做dp即可

    printf("%d\n", res);

    return 0;
}

dfs求树的直径

/*
枚举每个点，求每个点往下能走到的最远距离和次远距离，相加就是一种直径，从所有直径中取一个最大值，就是树的最大直径
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = N * 2;

int n;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int res; //最大直径

void add(int a, int b, int c) //头插法
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u, int father) //返回以u为根节点往下的最大深度
{
    //以u节点为根节点往下的最大深度和次大深度，求经过根节点的最大直径，因为是无向图，
    //所以只需找出根节点的最大深度和次大深度，相加即可
    //注：这里直接初始化成0，因为如果有负权边的话，那么加上一定会使直径变短，就不是最优解了，所以直接忽略负权边
    int d1 = 0, d2 = 0; 

    for(int i = h[u]; i != -1; i = ne[i]) //遍历所有子节点
    {
        int j = e[i];
        if(j == father) continue; //因为是无向图，所以不能往回遍历，不然会造成死循环

        int d = dfs(j, u) + w[i]; //以当前子节点为第二节点往下遍历的最大深度 + 根节点u到子节点j的距离(即权重)
        if(d >= d1) d2 = d1, d1 = d; //大于当前记录的最大值就更新最大值，原来的最大值就变成次大值
        else if(d > d2) d2 = d; //如果不大于最大值，但是大于次大值，直接更新次大值
    }

    res = max(res, d1 + d2); //更新最大直径

    return d1; //返回以u为根节点往下的最大深度
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 0; i < n - 1; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c); //无向图添加边
    }

    dfs(1, -1); //深搜

    printf("%d\n", res); //输出
    return 0;
}

两次bfs/dfs求树的直径

从任意一个节点出发，对树做一遍bfs/dfs，求出与出发点距离最远的节点，记为 $p$

从节点 $p$ 出发，再对树做一遍bfs/dfs，求出与 $p$ 距离最远的节点，记为 $q$

从 $p$ 到 $q$ 的路径就是树的一条直径。

由于模板题的数据是带父权值的，因此并不能根据题目写出模板代码，但是代码实现是很简单的，可以自行思考

可以参考 巡逻 的题解代码，用到了本算法。