점수 경주

문제

KOI 공원은 $11$번 지점부터 $NN$번 지점까지 $NN$개의 지점으로 구성되어 있으며, 두 지점을 잇는 $N-1N\; -\; 1$개의 도로가 있다. $ii$번째 도로는 $U_{i}U\_i$번 지점과 $V_{i}V\_i$번 지점을 이으며, 점수 $W_{i}W\_i$를 가진다($1\le i\le N-11\; \backslash le\; i\; \backslash le\; N\; -\; 1$).

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

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

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

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

$ii$번 지점에 대해, 해당 지점이 시작 지점일 때 최적 전략을 따랐을 때 참가자들의 최종 점수의 총합을 $S_{i}S\_i$라고 하자. 또한 그때 참가자들이 자신의 점수를 $00$점으로 바꾼 횟수의 총합을 $C_{i}C\_i$라고 하자.

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

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

• $22$번 지점이 목표 지점인 참가자는 $22$번 지점으로 이동하며 $-1-1$점을 받게 된다. 이후 $22$번 지점에서 자신의 점수를 $00$점으로 만든다. 최종 점수는 $00$점이다.
• $33$번 지점이 목표 지점인 참가자는 $33$번 지점으로 이동하며 $22$점을 받게 된다. 최종 점수는 $22$점이다.
• $44$번 지점이 목표 지점인 참가자는 $22$번 지점으로 이동하며 $-1-1$점을 받는다. 이후 $22$번 지점에서 자신의 점수를 $00$점으로 만든다. 이후 $44$번 지점으로 이동하며 $22$점을 받게 된다. 최종 점수는 $22$점이다.
• $55$번 지점이 목표 지점인 참가자는 $33$번 지점으로 이동하며 $22$점을 받는다. 이후 $55$번 지점으로 이동하며 $-3-3$점을 받는다. 이후 $55$번 지점에서 자신의 점수를 $00$점으로 만든다. 최종 점수는 $00$점이다.
• $66$번 지점이 목표 지점인 참가자는 $33$번 지점으로 이동하며 $22$점을 받는다. 이후 $66$번 지점으로 이동하며 $-1-1$점을 받게 된다. 최종 점수는 $11$점이다.

따라서 $S_1=5S\_1\; =\; 5$, $C_1=3C\_1\; =\; 3$이다.

$S_1,\cdots ,S_{N}S\_1,\backslash cdots,S\_N$ 및 $C_1,\cdots ,C_{N}C\_1,\backslash cdots,C\_N$을 구하는 프로그램을 작성하라.

입력

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

이후 $N-1N\; -\; 1$개의 줄에 걸쳐 $ii$번째 줄에는 $U_{i}U\_i$, $V_{i}V\_i$, $W_{i}W\_i$가 공백으로 구분되어 주어진다.

출력

$S_1,\cdots ,S_{N}S\_1,\backslash cdots,S\_N$만을 구한 경우

• 첫 번째 줄에 $00$을 출력한다.
• 두 번째 줄에 $S_1,\cdots ,S_{N}S\_1,\; \backslash cdots,\; S\_N$을 공백으로 구분하여 출력한다.

$S_1,\cdots ,S_{N}S\_1,\; \backslash cdots,\; S\_N$ 및 $C_1,\cdots ,C_{N}C\_1,\backslash cdots,C\_N$을 구한 경우

• 첫 번째 줄에 $11$을 출력한다.
• 두 번째 줄에 $S_1,\cdots ,S_{N}S\_1,\; \backslash cdots,\; S\_N$을 공백으로 구분하여 출력한다.
• 세 번째 줄에 $C_1,\cdots ,C_{N}C\_1,\; \backslash cdots,\; C\_N$을 공백으로 구분하여 출력한다.

6
1 2 -1
1 3 2
2 4 2
3 5 -3
3 6 -1

1
5 5 6 8 6 6
3 5 2 0 6 6

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

1
51 75 71 47 51 47 47 91 51 91
0 0 0 0 0 0 0 0 0 0

10
8 1 -2
10 5 -2
10 6 1
3 8 3
10 8 3
4 6 4
9 8 -5
9 7 5
6 2 -4

1
24 23 40 48 21 23 24 24 24 21
11 12 2 0 12 4 1 3 9 4