1072 树的最长路径（树形dp）

￡神魔★判官ぃ 2022-08-28 11:48 6阅读 0赞

**1. 问题描述：**

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

**输入格式**

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

**输出格式**

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

**数据范围**

1 ≤ n ≤ 10000，  
1 ≤ ai，bi ≤ n，  
−10 ^ 5 ≤ ci ≤ 10 ^ 5

**输入样例：**

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

**输出样例：**

22  
来源：[https://www.acwing.com/problem/content/description/1074/][https_www.acwing.com_problem_content_description_1074]

**2. 思路分析：**

树的路径也称为树的直径，求树的最大直径是经典的**树形dp**的问题。求树的直径有一种比较经典的做法：

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

具体的做法：首先任选一个节点，然后使用dfs遍历树中的每一个节点，在dfs的过程中求解每个子节点往下走的最大路径长度，这里主要分为两种情况：

*  当前节点u往下走的过程中是一条路走到黑，也即以当前的根节点往下走可以找到一条最长的路径==>路径的开始是当前的节点u
 *  最长的路径穿过了当前的节点u，这个时候我们就需要记录一下往下走的最长路径与次长路径的长度，两者相加就是穿过当前节点的最长路径

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16][]

由上面的两点可以知道我们在dfs的过程中需要记录一下当前节点往下走的最长路径与次长路径长度（两个较大值相加的结果才是最大的），所以我们需要在递归调用完dfs方法之后处理往下走的路径长度，使用两个变量d1，d2来记录当前节点往下走的最长路径与次长路径长度，这里可以使用一个技巧是一开始的时候声明d1 = d2 = 0，这样当我们遇到负数路径的时候是不会走这些路径的，也即不走，这样就可以解决路径是负数的问题，当当前节点u往下走的所有路径走完之后那么d1记录的就是最长路径，我们可以使用一个全局变量res来记录以当前根节点往下走的树的直径(res = max(res，d1 + d2))，每一次递归完当前节点往下走的所有路径之后更新一下res，当递归返回到上一层的时候回到的是某一个节点（也即在递归回溯的时候最终每一个节点都会返回到），这样就可以计算出每一个节点为根节点往下走或者是当前节点在某条路径的最长路径长度。

**3. 代码如下：**

**树形dp：**

from typing import List
    
    
    class Solution:
        res = 0
    
        # 因为是无向图所以在递归的时候使用fa来避免两个点重复搜索造成死循环的问题
        def dfs(self, u: int, fa: int, g: List[List[tuple]]):
            # d1, d2设置为0, 如果路径的权重为负数那么久不走了也即相当于是0
            d1, d2 = 0, 0
            for next in g[u]:
                # 如果是父节点跳过当前的父节点也即递归的时候是往下搜索的(无向图)
                if next[0] == fa: continue
                # 当前节点的子节点往下递归的最大权重加上当前父节点到子节点的权重
                d = self.dfs(next[0], u, g) + next[1]
                # 记录当前顶点往下走的最大权重与次大权重
                if d >= d1:
                    d2 = d1
                    d1 = d
                elif d >= d2:
                    d2 = d
            # 更新答案
            self.res = max(self.res, d1 + d2)
            return d1
    
        def process(self):
            # n表示节点的个数
            n = int(input())
            # 这里使用列表来创建无向图
            g = [list() for i in range(n + 1)]
            for i in range(n - 1):
                a, b, c = map(int, input().split())
                # 使用元组的好处是能存储边的终点以及对应的权重, 或者每一个列表是一个字典也可以
                # 因为是无向图所以需要创建两条边, 元组的第一个元素表示a-b的b或者是b-a的a, 第二个元素表示边的权重
                g[a].append((b, c))
                g[b].append((a, c))
            # 节点编号为1~n所以当前根节点的父节点为小于1的数即可, 在递归的时候任取一个根节点即可
            self.dfs(1, -1, g)
            return self.res
    
    
    if __name__ == "__main__":
        print(Solution().process())

![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

[https_www.acwing.com_problem_content_description_1074]: https://www.acwing.com/problem/content/description/1074/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/13cc40639309453eb2661bb41fbe69b3.png
[wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]: