题目地址：

https://www.acwing.com/problem/content/1074/

给定一棵树，树中包含 n n n个结点（编号 1 ∼ n 1\sim n 1∼n）和 n − 1 n−1 n−1条无向边，每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说，要找到一条路径，使得使得路径两端的点的距离最远。注意：路径中可以只包含一个点。

输入格式：
第一行包含整数 n n n。接下来 n − 1 n−1 n−1行，每行包含三个整数 a i , b i , c i a_i,b_i,c_i ai​,bi​,ci​，表示点 a i a_i ai​和 b i b_i bi​之间存在一条权值为 c i c_i ci​的边。

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

数据范围：
1 ≤ n ≤ 10000 1≤n≤10000 1≤n≤10000
1 ≤ a i , b i ≤ n 1≤a_i,b_i≤n 1≤ai​,bi​≤n
− 1 0 5 ≤ c i ≤ 1 0 5 −10^5≤c_i≤10^5 −105≤ci​≤105

先用邻接表建图，可以以任意点为树根，然后进行DFS。我们枚举以每个点为最高点时，经过该点的最长路径的长度。设该点编号为 x x x，并且从其出发向下（我们把整个图看成是一棵有根树）的所有路径的最大路径和为 f ( x ) f(x) f(x)，设 x x x的孩子们分别是 c 1 , . . . , c k c_1,...,c_k c1​,...,ck​，则有： f ( x ) = max ⁡ { f ( c i ) + ∣ ( x , c i ) ∣ } f(x)=\max\{f(c_i)+|(x,c_i)|\} f(x)=max{f(ci​)+∣(x,ci​)∣}不妨设使得 f ( c i ) + ∣ ( x , c i ) ∣ f(c_i)+|(x,c_i)| f(ci​)+∣(x,ci​)∣最大和次大的两个 c i c_i ci​分别是 c 1 c_1 c1​和 c 2 c_2 c2​而最长路径可以由 max ⁡ { 0 , f ( c 1 ) + ∣ ( x , c 1 ) ∣ } + max ⁡ { 0 , f ( c 2 ) + ∣ ( x , c 2 ) ∣ } \max\{0,f(c_1)+|(x,c_1)|\}+\max\{0,f(c_2)+|(x,c_2)|\} max{0,f(c1​)+∣(x,c1​)∣}+max{0,f(c2​)+∣(x,c2​)∣}，以上 ∣ ( x , c i ) ∣ |(x,c_i)| ∣(x,ci​)∣的意思是连接 x x x与 c i c_i ci​的边的长度。这里与 0 0 0取 max ⁡ \max max的意思是，如果从 x x x走某个孩子向下走的路径和是负数，那不如不添加这条路，不添加的时候就是 0 0 0。

有一个细节需要注意，由于上面的算法是取了某个点作为树根，然后将整棵树看成一个有根树了，所以在枚举每个点的时候要只计算从它向下走的路径，而不能再向上走。这里主要有两个办法做，要么开一个bool数组记录某个顶点是否被访问过，如果之前访问过就不再重复访问；要么可以将其父亲作为参数传进来，在遍历当前节点的邻接点的时候，略过其父亲节点。

代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010, M = 2 * N;
int n, res;
int h[N], e[M], ne[M], w[M], idx;

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

// 返回从u出发向下能走的权值和最大的路径的权值和
int dfs(int u, int parent) {
    int dist = 0;
    // 分别存最大和次大
    int d1 = 0, d2 = 0;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        // 略过父亲节点
        if (j == parent) continue;

        int d = dfs(j, u) + w[i];
        dist = max(dist, d);

        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }

    res = max(res, d1 + d2);

    return dist;
}

int main() {
    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c); 
    }

    dfs(1, -1);
    cout << res << endl;

    return 0;
}

时空复杂度 O ( n ) O(n) O(n)。