给定一棵树，树中包含 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分析：
dp算法: 以任何一个点出发, 找到距离该点最远的2条路径, 加起来就是结果. 由于用的是无向边, 所以dfs能够遍历到所有点所有边, 只需要把结果用全局变量更新即可.
简略证明:
1. 首先假设起点在最长路径上, 显然能得到最佳结果;
2. 而假设起点不在最长路径上, 那么在dfs走到最长路径上的某一点之前, 该条路径都不会是最长路径的一部分,
那么在到达最长路径上的某个点的时候也不会因为father的限制导致冲突, 所以到达那个点之后就还能正常算出最终结果.
AC代码 （Python3）
N = int(input())
Map = [dict() for i in range(N+1)]
# 注意这里空间卡的很死 必须要用邻接表来存图 用邻接矩阵会MLE
for i in range(N-1) :
come,to,weight = map(int,input().split())
Map[come][to] = weight
Map[to][come] = weight
ans = 0
def dfs(now_node,father) : # 当前节点 当前节点的父节点
global ans
dis = 0 # 当前节点能走到最远距离
d1,d2 = 0,0 # 最长路径 ，次长路径
tmp = 0 # 临时变量存距离
for i in Map[now_node].keys() :
if i == father :
continue
tmp = dfs(i,now_node) + Map[now_node][i] # 当儿子节点能走到的最远距离 + 当前节点到儿子节点的距离
dis = max(dis,tmp) # 更新当前节点能走到的最远距离
if tmp > d1 : d2 = d1 ; d1 = tmp # 更新最长路径
elif tmp > d2 : d2 = tmp # 更新次长路径
ans = max(ans,d1+d2) # 更新答案
return dis
dfs(1,-1) # 开始搜索 从任意一个节点开始即可 父节点处初始设为-1
print(ans)
