32074번 - 점수 경주 서브태스크점수

문제

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$만을 구한 경우

• 첫 번째 줄에 0ドル$을 출력한다.
• 두 번째 줄에 $S_1, \cdots, S_N$을 공백으로 구분하여 출력한다.

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

• 첫 번째 줄에 1ドル$을 출력한다.
• 두 번째 줄에 $S_1, \cdots, S_N$을 공백으로 구분하여 출력한다.
• 세 번째 줄에 $C_1, \cdots, C_N$을 공백으로 구분하여 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 2ドル \le N \le 300,000円$
• 1ドル \le U_i, V_i \le N$ $(1 \le i \le N - 1)$
• $-10,000円,000円 \le W_i \le 10,000円,000円$ $(1 \le i \le N - 1)$

서브태스크

힌트