트리 거리 그래프의 매칭

이 문제는 현재 ICPC 챔피언들을 위해 만들었다. 2020 ICPC 챔피언 중 한 명부터, 바라건대 2023 ICPC 챔피언까지, 그리고 2021 챔피언부터 바라건대 2022 챔피언까지 애정을 담아 바친다.

정점이 $n$개인 간선 가중치 트리 $T$가 주어진다. $d_{uv}$를 $T$에서 $u$와 $v$를 잇는 유일한 단순 경로 위 간선 가중치의 합으로 정의한다. 간선 $(u, v)$의 가중치가 $d_{uv}$인 완전 가중 그래프 $G$를 생각한다.

$1$부터 $\lfloor n/2 \rfloor$ 사이의 모든 $k$에 대해, 그래프 $G$에서 크기가 $k$인 매칭의 최대 가중치를 구하라. 크기가 $k$인 매칭은 두 간선이 정점을 공유하지 않는 간선 $k$개의 집합이다.

첫 줄에 정수 $n$ ($2 \le n \le 100\,000$)이 주어진다. 트리의 정점 수이다.

다음 $n-1$개의 줄 중 $i$번째 줄에는 정수 $u_i$, $v_i$, $w_i$ ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^8$)가 주어진다. 이는 $T$에 가중치가 $w_i$인 간선 $(u_i, v_i)$가 있다는 뜻이다.

주어지는 간선들은 트리를 이룸이 보장된다.

$\lfloor n/2 \rfloor$개의 정수를 출력하라. 각 정수는 대응하는 크기의 매칭이 $G$에서 가질 수 있는 최대 가중치이다.