점수 경주 | cho.sh

KOI 공원은 $1$번 지점부터 $N$번 지점까지 $N$개의 지점으로 구성되어 있으며, 두 지점을 잇는 $N - 1$개의 도로가 있다. $i$번째 도로는 $U_i$번 지점과 $V_i$번 지점을 이으며, 점수 $W_i$를 가진다($1 \le i \le N - 1$).

KOI 공원에서는 어떤 두 지점이든 도로를 따라 서로 이동할 수 있다. 즉, KOI 공원은 트리 구조를 이룬다.

KOI 공원에서 점수 경주를 하려고 한다. 점수 경주는 다음과 같이 이루어진다.

총 $N - 1$명의 참가자가 시작 지점에서 출발해, 각자 시작 지점을 제외한 서로 다른 $N - 1$개의 지점으로 단순 경로를 따라 이동한다.
각 참가자는 처음에 $0$점의 점수를 가지고 있다.
각 도로에 대해, 해당 도로를 지나면 그 도로의 점수만큼 점수를 받게 된다.
참가자들은 어떤 지점에서든 자신의 점수를 $0$점으로 만들 수 있다. 자신의 목표 지점으로 도착한 후에도 가능하다.

어떤 참가자의 최종 점수를 최대화하는 방법의 하나로는 어떤 지점에서 점수가 $0$점 미만이 될 때마다 $0$점으로 바꾸는 방법이 있다. 이를 최적 전략이라고 하자. 참가자들은 모두 최적 전략을 따르기로 하였다.

$i$번 지점에 대해, 해당 지점이 시작 지점일 때 최적 전략을 따랐을 때 참가자들의 최종 점수의 총합을 $S_i$라고 하자. 또한 그때 참가자들이 자신의 점수를 $0$점으로 바꾼 횟수의 총합을 $C_i$라고 하자.

예를 들어, KOI 공원의 모습이 다음과 같을 때, $1$번 지점이 시작 지점인 경우를 생각해 보자.

최적 전략을 따를 때, 점수 경주의 과정은 다음과 같다.

$2$번 지점이 목표 지점인 참가자는 $2$번 지점으로 이동하며 $-1$점을 받게 된다. 이후 $2$번 지점에서 자신의 점수를 $0$점으로 만든다. 최종 점수는 $0$점이다.
$3$번 지점이 목표 지점인 참가자는 $3$번 지점으로 이동하며 $2$점을 받게 된다. 최종 점수는 $2$점이다.
$4$번 지점이 목표 지점인 참가자는 $2$번 지점으로 이동하며 $-1$점을 받는다. 이후 $2$번 지점에서 자신의 점수를 $0$점으로 만든다. 이후 $4$번 지점으로 이동하며 $2$점을 받게 된다. 최종 점수는 $2$점이다.
$5$번 지점이 목표 지점인 참가자는 $3$번 지점으로 이동하며 $2$점을 받는다. 이후 $5$번 지점으로 이동하며 $-3$점을 받는다. 이후 $5$번 지점에서 자신의 점수를 $0$점으로 만든다. 최종 점수는 $0$점이다.
$6$번 지점이 목표 지점인 참가자는 $3$번 지점으로 이동하며 $2$점을 받는다. 이후 $6$번 지점으로 이동하며 $-1$점을 받게 된다. 최종 점수는 $1$점이다.

따라서 $S_1 = 5$, $C_1 = 3$이다.

$S_1,\cdots,S_N$ 및 $C_1,\cdots,C_N$을 구하는 프로그램을 작성하라.

첫 번째 줄에 $N$이 주어진다.

이후 $N - 1$개의 줄에 걸쳐 $i$번째 줄에는 $U_i$, $V_i$, $W_i$가 공백으로 구분되어 주어진다.

$S_1,\cdots,S_N$만을 구한 경우

$S_1, \cdots, S_N$ 및 $C_1,\cdots,C_N$을 구한 경우