树的最长路径

树直径 DFS 树形dp

题目

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

输入格式

第一行包含整数 $\mathbf{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$

样例

input

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

output

22

思路

带权无向边树的直径就是树的最长路径。若不带权则是边数最长的路径。

1. 任取一点作为起点，找到距离该点最远的一个点u。
2. 再找到距离u最远的一点v。 那么u和v之间的路径就是一条直径。

一般都用BFS来求解, 因为DFS的递归栈空间不一定够使。

涉及离散数学 证明： 先证明第一步找到的u是某一条直径的起点 已经确定起点之后, 根据定义显然其结尾就是距离起点最远的点v。 如果边权是正数则可以直接用BFS求解。

这里是负数, 故需要使用动态规划, 在所有路径中找最大的一个。 状态表示：那么f[i]就是以i点为最高点的所有路径的最长长度。 状态计算： 把每个直径用它高度最高的点来分类 对于每个点u我们考虑他的子节点 存在很多直径情况： ① 以u点为开始（结尾） 只需要枚举每个子节点往下走的最大长度,然后加上u到子节点的距离即可 ② 穿过了u点只需要找到u到子节点子树内部路径中的最长一个+次长的一个, 那么和就是最长的一个

对于最大值和次大值, 可以用循环来求, 如果当前值大于最大值, 则将最大值赋值给次大值, 当前值赋值给最大值。若当前值小于等于最大值且大于次大值, 则直接更新次大值即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e4 +10, M = 2*N;
int h[N], e[M], ne[M], w[M], idx;
int n,res;
 
void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
int dfs(int u, int fa)
{
     int dist = 0;
     int d1 = 0, d2 = 0;
     
     for(int i = h[u]; ~i; i = ne[i])
     {
         int j = e[i];
         if(j == fa) 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()
{
    cin >> n;
    memset(h, -1, sizeof h);
    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;
}