점수 경주
다이아몬드 II의견: 0
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\)을 공백으로 구분하여 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 2점 | \(N \le 1\,000\). |
2 | 6점 | \(0 \le W_i \le 5\) (\(1 \le i \le N - 1\)). |
3 | 20점 | \(0 \le W_i \le 5\) 또는 \(W_i \le -1\,000\,000\) (\(1 \le i \le N - 1\)). |
4 | 4점 | \(U_i = 1\), \(V_i = i + 1\) (\(1 \le i \le N - 1\)). |
5 | 10점 | \(U_i = i\), \(V_i = i + 1\) (\(1 \le i \le N - 1\)). |
6 | 16점 | \(U_i = \left\lfloor \dfrac{i+1}{2} \right\rfloor\), \(V_i = i + 1\) (\(1 \le i \le N - 1\)). |
7 | 18점 | 세 개 이상의 다른 지점과 도로로 연결된 지점은 최대 두 개이다. |
8 | 24점 | 추가 제약 조건 없음. |
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
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2024 > 2차 대회 > 고등부 4번
평가 및 의견
점수 경주
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
점수 경주