<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

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

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

输入格式

第一行包含整数 $n$。

接下来 $n-1$ 行，每行包含三个整数 $a_i,b_i,c_i$，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。

输出格式

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

数据范围

$1 \le n \le 10000$,
$1 \le a_i,b_i \le n$,
$-10^5 \le c_i \le 10^5$

输入样例：

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

输出样例：

22

思路

闫氏$DP$分析法：

状态表示：$f_{0/1,i}$

• 集合：以节点$i$为根的子树中，从子树某一个节点到$i$的最长路为$f_{0,i}$，次长路为$f_{1,i}$
• 属性：$\max$

状态计算：

• 如果子节点的最长路加上对应边后大于当前的最长路，那么就更新最长路
• 否则如果大于次长路，那么就更新次长路
• 所以状态转移方程就是$\begin{cases}f_{0,i}=\underset{s\in son_i}\max\lbrace f_{0,s}+w_{i,s}\rbrace\newline f_{1,i}=\underset{s \in son_i~\text{and}~f_{0,s}+w_{i,s}< f_{0,i}}\max\lbrace f_{0,s}+w_{i,s}\rbrace\end{cases}$

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010,M = 2 * N;
int n;
int h[N],e[M],ne[M],w[M],idx;
int f[2][N];
int ans = 0;
void add (int a,int b,int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs (int u,int fa) {
    for (int i = h[u];~i;i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs (j,u);
        if (f[0][j] + w[i] > f[0][u]) f[1][u] = f[0][u],f[0][u] = f[0][j] + w[i];
        else if (f[0][j] + w[i] > f[1][u]) f[1][u] = f[0][j] + w[i];
    }
    ans = max (ans,f[0][u] + f[1][u]);
}
int main () {
    memset (h,-1,sizeof (h));
    cin >> n;
    for (int i = 1;i <= n - 1;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        add (a,b,c),add (b,a,c);
    }
    dfs (1,-1);
    cout << ans << endl;
    return 0;
}