1073 树的中心（树形dp）

左手的ㄟ右手 2022-09-13 11:23 188阅读 0赞

**1. 问题描述：**

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

**输入格式**

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

**输出格式**

输出一个整数，表示所求点到树中其他结点的最远距离。

**数据范围**

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

**输入样例：**

5  
2 1 1  
3 2 1  
4 3 1  
5 1 1

**输出样例：**

2  
来源：[https://www.acwing.com/problem/content/1075/][https_www.acwing.com_problem_content_1075]

**2. 思路分析：**

由题目可知，我们需要在所有当前点到其余点中最远的距离中找出最短的那个距离，所以这个点应该是靠近中心的一个距离，这样才可以使得到其余点的距离是最近的。所以我们的目标是求解出从当前节点出发往上走与往下走的最长路径，求解出每一个节点向上走与向下走的最长路径取一个min即可，对于树中节点的最远距离可以分为两大类：

*  向下走的最远距离
 *  向上走的最短距离

对于第一类向下走的距离其实很简单，直接使用dfs遍历节点求解即可，然后在递归回溯的时候将子节点的信息往父节点的信息传递，更新每一条父节点往子节点路径的最远距离即可，问题是如何求解往上走的最远距离，例如下图中2往上走的最短距离，2的父节点是3，对于节点3又可以往下走或者往上走（3->2..，3->4...，3->1），对于2往上走的最远距离应该是父节点3往上走与往下走的最远距离的较大值，而2往上走到3的时候已经求解出3往上走的最远距离了，所以求解出3往下走的最远距离取一个max即可，但是对于3往下走的最远距离有可能是往2这个节点走的，而2这个节点是不能够走的（路径重合了），3节点往下走的时候必须是除了2这个子节点往下走的其余子节点路径的最大值，也即次大值，所以我们在求解往下走最远距离的时候需要记录每一个节点往下走的最远距离与次远距离（使用一维数组d1，d2来记录），由于在求解往上走最远距离的时候需要先判断一下父节点往下走的最远距离对应的路径是否包含了当前的节点，如果包含了当前节点那么使用次远距离进行更新，所以还需要记录当前节点往下走的最远距离对应的是哪一个子节点（使用一维数组p1来记录），其实画一个图就可以将代码很快写出来了。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # d1表示向下走的最长路径, d2表示向下走的次长路径, up表示向上走的最长路径, isLeaf判断是否是叶子节点
        d1, d2, up, p1, isLeaf = None, None, None, None, None
        INF = 10 ** 9
    
        # 求解d1, d2, fa用来判断是否是父节点(无向边创建的双向边为了避免死循环的问题传递fa参数, 这样可以保证是一直往下递归的)
        def dfs_d(self, u: int, fa: int, g: List[List[tuple]]):
            self.d1[u] = self.d2[u] = -self.INF
            # next[0]表示a-->b中的顶点b, next[1]表示a-->b的权重为c
            for next in g[u]:
                # 当前节点是父节点直接跳过
                if next[0] == fa: continue
                # 因为需要知道子节点的信息然后更新到父节点所以先要递归然后再往上传递信息
                d = self.dfs_d(next[0], u, g) + next[1]
                if d > self.d1[u]:
                    self.d2[u] = self.d1[u]
                    self.d1[u] = d
                    self.p1[u] = next[0]
                elif d > self.d2[u]:
                    self.d2[u] = d
            # 因为一开始的是将节点的距离置为负无穷, 最后叶子节点的时候也是负无穷所以最后在叶子节点往上返回的时候需要将叶子节点往下走的最长距离与次长距离置为0
            if self.d1[u] == -self.INF:
                self.d1[u] = self.d2[u] = 0
                self.isLeaf[u] = 1
            return self.d1[u]
    
        # 求解向上走的最长路径, 递归的时候是先更新节点信息再递归
        def dfs_u(self, u: int, fa: int, g: List[List[tuple]]):
            for next in g[u]:
                if next[0] == fa: continue
                if self.p1[u] == next[0]:
                    self.up[next[0]] = max(self.up[u], self.d2[u]) + next[1]
                else:
                    self.up[next[0]] = max(self.up[u], self.d1[u]) + next[1]
                self.dfs_u(next[0], u, g)
    
        def process(self):
            n = int(input())
            # 顶点编号从1开始, python3使用列表来建图
            g = [list() for i in range(n + 1)]
            for i in range(n - 1):
                a, b, c = map(int, input().split())
                # 无向图, 使用元组封装边的终点以及权重
                g[a].append((b, c))
                g[b].append((a, c))
            # 初始化
            self.d1 = [0] * (n + 1)
            self.d2 = [0] * (n + 1)
            self.up = [0] * (n + 1)
            self.isLeaf = [0] * (n + 1)
            # p1[u]表示节点u往下走的最长路径是哪一个子节点, 这样在求解向上走的路径的时候可以判断出属于哪一种情况
            self.p1 = [0] * (n + 1)
            self.dfs_d(1, -1, g)
            self.dfs_u(1, -1, g)
            res = self.INF
            for i in range(1, n + 1):
                # 判断是否是叶子节点, 如果是叶子节点那么只有向上走的最远路径
                if self.isLeaf[i]:
                    res = min(res, self.up[i])
                else:
                    res = min(res, max(self.up[i], self.d1[i]))
            return res
    
    
    if __name__ == '__main__':
        print(Solution().process())

[https_www.acwing.com_problem_content_1075]: https://www.acwing.com/problem/content/1075/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/aa5c9e0029a54c42abf24b4de88d7c26.png