$$\color{Red}{树的最长路径 步骤详解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

输入格式

第一行包含整数 n。

接下来 n−1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。

输出格式
输出一个整数，表示树的最长路径的长度。

数据范围

1≤n≤10000

1≤ai,bi≤n

−105≤ci≤105

输入样例：

6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

输出样例：

22

思考

找寻树的最长路径的通用途径：任意选取一点，找寻距离它最远的点，然后找寻这个点距离它最远的点，这两个点连成的线即为树的直径。

为什么？
假设任意选取点a,距离它最远的点是点b。不妨采用反证法，证明任选点的距离最远点是直径，假设真正的直径是c和d两个点。
树必是联通的，我们假设a和b之间存在一点x，c和d之间存在一点y，这两个点相连。
由a和b距离最远可得: (a, x, b) > (a, x, y, d)，我们把公共的部分(a, x)去掉，即(x, b) > (x, y, d)，显然此时存在矛盾，因为(c, y, x, b) > (c, y, d)的距离，即直径不是最长的，故证毕。
当x和y重合时仅为特例，此时显然满足(x, b) > (x, d)故(c, x, d)没有(c, x, b)长，所以这么选取的点b必然是直径的一个起点。

本题的思路是动态规划，把集合按树的节点划分，枚举每个节点，代表集合为经过这个节点为最高的树节点即根节点的一条条路径，属性存储为最大值和次大值，这样就可以满足这两条边组成的路径是最长的一条路径。

而因为dfs可以一直遍历到叶子节点的末尾，从叶到根一层层把值找到，并循环的找寻满足的最长边和次长边的和的最大值，最终回溯到起始点的时候，即找到满足的最终答案。

JAVA代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 10010, n, idx;
    static int[] e = new int[2 * N];
    static int[] ne = new int[2 * N];
    static int[] h = new int[N];
    static int[] w = new int[2 * N];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] += c;
        h[a] = idx++;
    }
    static int ans = 0;

    static int dfs(int u, int father){
        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];
            if (d >= d1){
                d2 = d1;
                d1 = d;
            }else if (d > d2) d2 = d;
        }
        ans = Math.max(ans, d1 + d2);
        return d1;
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a, b, c);
            add(b, a, c);
        }
        dfs(1, -1);
        System.out.println(ans);
    }
}