페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8020
서브태스크

점수 경주 6.5초 1024MB

문제

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을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.

  • 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)


입력

첫 번째 줄에 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을 공백으로 구분하여 출력한다.

각 부분문제에 대해, S_1,\cdots,S_N만을 구한 경우 해당 부분문제의 점수의 절반을 얻을 수 있다. 그 방법에 대해서는 출력 형식을 참고하라.  

S_1,\cdots,S_N 및 C_1,\cdots,C_N을 구한 경우, S_1,\cdots,S_N이 정확해도 C_1,\cdots,C_N이 정확하지 않다면 점수를 받을 수 없음에 유의하라.


부분문제

번호 점수 조건
#12점

N \le 1,000 

#26점

0 \le W_i \le 5(1 \le i \le N - 1)

#320점

0 \le W_i \le 5 또는 W_i \le -1,000,000(1 \le i \le N - 1)

#44점

U_i = 1, V_i = i + 1(1 \le i \le N - 1)

#510점

U_i = i, V_i = i + 1(1 \le i \le N - 1)

#616점

U_i = \lfloor \frac{i + 1}{2} \rfloor, V_i = i + 1(1 \le i \le N - 1)

#718점

세 개 이상의 다른 지점과 도로로 연결된 지점은 최대 두 개이다.

#824점

추가 제약 조건 없음.


예제1

입력
6
12-1
132
242
35-3
36-1
출력
1
556866
352066

예제2

입력
10
5105
475
161
895
941
670
510
293
433
출력
1
51757147514747915191
0000000000

예제3

입력
10
81-2
105-2
1061
383
1083
464
98-5
975
62-4
출력
1
24234048212324242421
1112201241394

출처

2024 KOI 2차 고4

역링크