暴力思考方式

• 遍历n个点，每个点做一遍dfs，得到每个点的最远距离
• 时间复杂度为O(N ^ 2)

树形DP

从u到其他点的距离可以分为两个
- 一类是从u点向下走的最远距离，用d1[u]表示
- 一类是从u点向上走的最远距离，用up[u]表示
- 从u到其他点的最远距离为max(d1[u], up[u])
- 从中心到其他点的最远距离为min(max(d1[i], up[i]))

从u点向下走的最远距离d1[u]
- 自下而上递推，由子节点的信息更新父节点的信息
- 从u点向下走的最大长度：d1[u] = d1[j] + w[i]
- 从u点向下走的次大长度：d2[u] = d2[j] + w[i]
- 也就是说，在返回时实现，即在dfs之后实现

**从u点向上走的最远距离为up[u]
- 自上而下递推，由父节点信息更新子节点信息
- 如果j在从u点向下走的最长路径上，up[j] = w[i] + max(up[u], d2[u])，画图理解，要么最长路径是向上走的，要么最长路径在u点拐弯朝着u点向下的次长路径走
- 如果j不在u点向下走的最长路径上，up[j] = w[i] + max(up[u], d1[u])
- 也就是说，在下行时实现，即在dfs之前实现
- 解释一下为什么这样分类：因为从u点出发的最长距离有两种情况：向上和向下

code

from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
# print = sys.stdin.write

def dfs_d(u, father):
    d1[u] = d2[u] = 0

    for j, w in graph[u]:
        if j == father:
            continue
        d = dfs_d(j, u) + w  # dfs(j, u)得到的是j点向下走的最远距离， w是u到j的距离，因此d就是u向下走的最远距离
        if d >= d1[u]:
            p1[u] = j  # 需要记录路径
            d2[u] = d1[u]
            d1[u] = d
        elif d > d2[u]:
            d2[u] = d
    return d1[u]

def dfs_u(u, father):
    for j, w in graph[u]:
        if j == father:
            continue

        if p1[u] == j:  # 表明j点在最长路径上
            up[j] = max(up[u], d2[u]) + w
        else:
            up[j] = max(up[u], d1[u]) + w
        dfs_u(j, u)

n = int(input().strip())

graph = defaultdict(list)
for i in range(n - 1):
    a, b, c= map(int, input().strip().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

d1 = [0 for _ in range(n + 1)]  # 记录的是每个点向下走的最远距离
d2 = [0 for _ in range(n + 1)]  # 次远
p1 = [0 for _ in range(n + 1)]  # 记录的是从每个点向下走的最远距离的时候是经过哪个点的
up = [0 for _ in range(n + 1)]  # 记录每个点向上走的最远距离
dfs_d(1, -1)
dfs_u(1, -1)
res = float("inf")
for i in range(1, n + 1):
    if max(d1[i], up[i]) < res:
        res = max(d1[i], up[i])
print(res)