g7-07693. 带权树的直径 · 林老师的题库

题目描述

给定一棵 $n$ 个结点的带权无向树，结点编号为 $1, 2, \dots, n$ 。第 $i$ 条边连接结点 $u_{i}$ 与 $v_{i}$ ，边权为 $w_{i}$ 。

树上两点之间有唯一一条简单路径，路径的长度定义为这条路径上所有边的边权之和。树中长度最大的路径称为树的直径，请你求出直径的长度。

第一行一个整数 $n$ 。

接下来 $n - 1$ 行，每行三个整数 $u, v, w$ （ $1 \leq u, v \leq n$ ， $1 \leq w \leq 1 0^{9}$ ），表示结点 $u$ 与结点 $v$ 之间有一条边权为 $w$ 的边。

保证这些边构成一棵树。

输出一行一个整数，表示树的直径长度。

输入

输出

样例解释：路径 $4 \to 3 \to 2 \to 5 \to 6$ 的长度为 $5 + 4 + 10 + 2 = 21$ ，它是所有路径中最长的一条。

对于 $100%$ 的数据， $1 \leq n \leq 2 \times 1 0^{5}$ ， $1 \leq w \leq 1 0^{9}$ 。

答案可能超过 $2^{31} - 1$ ，请使用 $64$ 位整数（C++ 中的 long long）。

本题共 $10$ 个测试点，每个测试点 $10$ 分。