Tree Diameter

AC一覧

Problem Statement
問題文

$N$ 頂点の重み付き無向木が与えられる. $i$ 番目の辺は,頂点 $a_i$,$b_i$ 間に双方向に張られており,重みは $c_i$ である.

最遠頂点対 $(u, v)$ を一つ構築し,$u$ から $v$ へのパスを出力せよ.

Constraints
制約

Input
入力

$N$
$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$ はパスの重みの総和,$Y$ はパスに含まれる頂点数を表す. $u_i$,$u_{i+1}$ はそれぞれ $i+1$ 番目に通る辺の始点と終点を表す.

Sample
サンプル

# 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

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions