8226: [yosupo] Tree - Tree Diameter
[Creator : ]
Description
You are given a weighted undirected tree with $N$ vertices.The $i$-th edge bidirectionally connects vertices $a_i$ and $b_i$, and its weight is $c_i$.
Find a pair of vertices $(u, v)$ that are farthest apart, and output the path from $u$ to $v$.
Find a pair of vertices $(u, v)$ that are farthest apart, and output the path from $u$ to $v$.
Input
$N$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_{N-2}$ $b_{N-2}$ $c_{N-2}$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
$\vdots$
$a_{N-2}$ $b_{N-2}$ $c_{N-2}$
Output
$X$ $Y$
$u_0$ $u_1$ $\ldots$ $u_{Y-1}$
$X$ is the sum of weights on the path, and $Y$ is the number of vertices on the path.$u_i$ and $u_{i+1}$ are the starting and ending vertices of the $i+1$-th edge traveled.
$u_0$ $u_1$ $\ldots$ $u_{Y-1}$
$X$ is the sum of weights on the path, and $Y$ is the number of vertices on the path.$u_i$ and $u_{i+1}$ are the starting and ending vertices of the $i+1$-th edge traveled.
Constraints
All input are integers.
$1 \leq N \leq 500,000$
$0 \leq a_i, b_i \leq N - 1$
$a_i \neq b_i$
$1 \leq c_i \leq 10^9$
$1 \leq N \leq 500,000$
$0 \leq a_i, b_i \leq N - 1$
$a_i \neq b_i$
$1 \leq c_i \leq 10^9$
Sample 1 Input
8
0 1 5
1 2 3
2 3 1
1 4 2
4 7 4
1 5 7
2 6 5
Sample 1 Output
15 4
6 2 1 5