树直径（Tree Diameter）

问题描述

给你一棵含 $N$ 个顶点的带权无向树。第 $i$ 条边（$0 \le i < N-1$）双向连接顶点 $a_i$ 和 $b_i$，边权为 $c_i$。
请找出一对顶点 $(u, v)$，使得它们之间的距离最远（即树的直径），并输出从 $u$ 到 $v$ 的路径。

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 5 \times 10^5$
• $0 \leq a_i, b_i \leq N-1$
• $a_i \ne b_i$
• $1 \leq c_i \leq 10^9$

输入格式

$N$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
:
$a_{N-2}\ b_{N-2}\ c_{N-2}$

输出格式

$X\ Y$
$u_0\ u_1\ \dots\ u_{Y-1}$

其中：

• $X$ 是路径上所有边权之和；
• $Y$ 是路径上的顶点数量；
• $u_i$ 与 $u_{i+1}$ 是第 $i+1$ 条被经过的边的两个端点（即路径顶点序列）。

8
0 1 5
1 2 3
2 3 1
1 4 2
4 7 4
1 5 7
2 6 5

15 4
6 2 1 5