当前位置: 代码迷 >> 综合 >> AcWing 树形DP相关问题 1073. 树的中心
  详细解决方案

AcWing 树形DP相关问题 1073. 树的中心

热度:54   发布时间:2024-02-05 19:14:43.0
N = int(input())link = {}
for i in range(1, N):a, b, w = map(int, input().split())if a not in link:link[a] = []if b not in link:link[b] = []link[a].append((b, w))link[b].append((a, w))# 随便选一个节点作为树的根,递归算每个节点到以这个节点为根的子树上的叶子的
# 最大距离,向上一层返回该最大距离,上一层节点就可以根据其所有子树向其返回
# 的最大距离来组合出一条经过该节点中转的最长直径,用该直径的长度更新全局
# 的最大直径长度即可, 每个树上的节点都对应了一个以该节点中转的直径的集合
# 此算法那对于权值为正负零均可处理ans = [0]  # 定义单独一个点也是有路径的,路径长度是1, 全局最大值就初始化为1def dfs(root, prev=None):# 最大值和次大值max1, max2 = 0, 0 # 最大值和次大值初始值设置为0, 可以直接避免掉负边带来的负面影响,默认可以看做每个节点都连接了无数个隐性的空节点,且边全权为0for child, path_len in link[root]:if child == prev:continuemax_len = dfs(child, root) + path_lenif max_len > max1:max2 = max1max1 = max_lenelif max_len > max2:max2 = max_lenans[0] = max(ans[0], max1 + max2)return max1dfs(1)
print(ans[0])