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/
2. 思路分析
树的路径也称为树的直径 求树的最大直径是经典的树形dp的问题。求树的直径有一种比较经典的做法
任取一个点作为起点 找到距离该点最短的一个点u再找到距离u最远的一个点v 那么u v之间的路径就是一条直径具体的做法 首先任选一个节点 然后使用dfs遍历树中的每一个节点 在dfs的过程中求解每个子节点往下走的最大路径长度 这里主要分为两种情况
当前节点u往下走的过程中是一条路走到黑 也即以当前的根节点往下走可以找到一条最长的路径 路径的开始是当前的节点u最长的路径穿过了当前的节点u 这个时候我们就需要记录一下往下走的最长路径与次长路径的长度 两者相加就是穿过当前节点的最长路径由上面的两点可以知道我们在dfs的过程中需要记录一下当前节点往下走的最长路径与次长路径长度 两个较大值相加的结果才是最大的 所以我们需要在递归调用完dfs方法之后处理往下走的路径长度 使用两个变量d1 d2来记录当前节点往下走的最长路径与次长路径长度 这里可以使用一个技巧是一开始的时候声明d1 d2 0 这样当我们遇到负数路径的时候是不会走这些路径的 也即不走 这样就可以解决路径是负数的问题 当当前节点u往下走的所有路径走完之后那么d1记录的就是最长路径 我们可以使用一个全局变量res来记录以当前根节点往下走的树的直径(res max(res d1 d2)) 每一次递归完当前节点往下走的所有路径之后更新一下res 当递归返回到上一层的时候回到的是某一个节点 也即在递归回溯的时候最终每一个节点都会返回到 这样就可以计算出每一个节点为根节点往下走或者是当前节点在某条路径的最长路径长度。
3. 代码如下
树形dp
from typing import List
