24968번 - 트리의 간선 바꾸기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (하단 참고) | 512 MB | 16 | 8 | 5 | 45.455% |
문제
Bob은 최근 트리를 이용한 점수 놀이를 즐겨하는데, 임의의 트리 $S$에 대한 점수 ($Score(S)$)는 아래와 같이 정의한다:
- 임의의 (무방향) 트리 $S$의 간선은 길이가 양의 정수인 가중치를 갖고 있다고 가정한다.
- 트리 $S$에 속한 서로 다른 정점 $x$, $y$가 있을 때, $Dist(x, y) := x$와 $y$사이의 최단 거리라 정의하자. 이 때, $P(x, y)$가 $x$와 $y$ 사이의 (고유한) 최단 경로라면, $P(x, y)$에 속한 간선들의 가중치 합이 최단 거리가 된다.
- 그러면 $Score(S) := \sum_{x, y \in S, x \neq y} {Dist(x, y)}$ 로 정의된다. 즉, 어떤 트리의 점수는 해당 트리에 속한 모든 서로 다른 노드 쌍의 최단 거리의 총합이다. $S$의 노드 개수가 $2$개 미만인 경우, $Score(S)$ 는 $0$으로 정의한다.
예를 들어, 아래의 트리에는 노드가 $3$개 있다.
- 위 정의에 따라 $Dist(1, 2) = 10$, $Dist(2, 3) = 20$, $Dist(1, 3) = 30$이다.
- 따라서 이 트리의 점수는 $10 + 20 + 30 = 60$이 된다.
Alice는 Bob의 놀이를 지켜보던 중 새로운 놀이를 제안했다. 우선, 둘은 함께 $n$개의 노드와 $n-1$개의 간선으로 구성된 트리를 하나 만드는데, 이를 $T_0$라 하고 "기본 트리"라 부른다. 편의상 기본 트리 $T_0$의 노드는 $1$부터 $n$까지 번호가 붙어있고, $n-1$개의 간선도 $1$부터 $n-1$까지 번호가 붙어있다 (이는 후술할 "간선 바꾸기"에 사용되는 간선의 인덱스이다). $T_0$의 $i$번째 간선을 $E[i] = (v, w, d)$라 하면, 이 간선은 노드 $v$와 노드 $w$를 잇고, 길이가 $d$인 간선을 나타낸다. 예를 들어, $E[1] = (1, 2, 10)$, $E[2] = (2, 3, 20)$ 이라면, 위 그림과 같은 트리가 얻어지고, 구체적으로 $(1, 2)$를 잇는 간선의 인덱스는 $1$이고 $(2, 3)$을 잇는 간선의 인덱스는 $2$이다.
이후, Alice가 "간선 바꾸기"를 $T_0$에 적용하면, Alice가 원하는 간선 하나를 $T_0$에서 지운 뒤, 새로운 간선을 하나 추가하여 새로운 트리를 만든다. 구체적으로, Alice는 총 $m$번의 "간선 바꾸기"를 시도해서 $T_0$으로부터 $m$개의 새로운 트리를 얻어내는데 이를 $T_1$, $T_2$, $\dots$, $T_m$이라 하자.
- $j$번째 "간선 바꾸기"를 위해 Alice는 총 4개의 정수를 Bob에게 알려준다 ($j = 1, 2, \dots, m$):
- $A[ j ]$: $T_0$의 간선 인덱스를 나타내며, $T_0$에서 삭제될 간선이다. 즉, $E[ A[ j ] ] = (v, w, d)$라면 $v$와 $w$를 잇는 간선을 지운다.
- $x[ j ]$, $y[ j ]$: 새로 추가할 간선이 잇게될 두 노드이다. ($x[ j ] \ne y[ j ]$)
- $z[ j ]$: 새로 추가할 간선의 길이이다.
- $T_0$ 에서 인덱스가 $A[ j ]$인 간선을 삭제하고 이후 $(x[ j ], y[ j ])$를 연결하는 길이 $z[ j ]$인 간선을 추가하여 얻어진 그래프를 $T_j$ 라 하자. ($j = 1, 2, \dots, m$) 이 문제에서 $T_j$ 는 언제나 트리임이 보장된다. 이 문제에서 $T_j$는 "$j$번째 변형 트리"라 부르자.
- 각각의 "간선 바꾸기"는 처음 만든 기본 트리인 $T_0$에 독립적으로 적용된다 (아래 예제 참고).
예를 들어 기본 트리인 $T_0$은 앞선 예제와 같이 $E[1] = (1, 2, 10)$, $E[2] = (2, 3, 20)$으로 구성된 트리라 하자. Alice가 총 $m = 4$번에 걸쳐 간선 바꾸기를 적용하는데, $A = [1, 1, 2, 2]$, $x = [3, 1, 2, 3]$, $y = [1, 3, 3, 1]$, $z = [1, 20, 30, 30]$이라 하자. 아래 $4$개의 그림은 좌측부터 순서대로 $1$~$4$번째 "간선 바꾸기"를 $T_0$에 각각 적용해서 얻어진 $T_j$와 해당 트리의 점수를 나타낸다. 그림에서 점선으로 표시된 간선은 "삭제된" 간선을 나타내고, 두꺼운 선으로 표시된 간선은 "추가된" 간선을 나타낸다.
- $T_1$: $T_0$에서 $1$번 간선 ($E[1]$)을 삭제하고, $3$과 $1$을 연결하는 길이가 $1$인 간선이 추가되었다. $Score(T_1) = 42$이다. ($T_j$ 점수 중 최솟값)
- $T_2$: $T_0$에서 $1$번 간선 ($E[1]$)을 삭제하고, $1$과 $3$을 연결하는 길이가 $20$인 간선이 추가되었다. $Score(T_2) = 80$이다. ($T_j$ 점수 중 최댓값)
- $T_3$: $T_0$에서 $2$번 간선 ($E[2]$)을 삭제하고, $2$와 $3$을 연결하는 길이가 $30$인 간선이 추가되었다. $Score(T_3) = 80$이다. ($T_j$ 점수 중 최댓값) 이 경우, 삭제된 간선과 추가된 간선이 같은 쌍의 노드를 연결하고 있고, 이러한 "간선 바꾸기"도 가능하다.
- $T_4$: $T_0$에서 $2$번 간선 ($E[2]$)을 삭제하고, $3$과 $1$을 연결하는 길이가 $30$인 간선이 추가되었다. $Score(T_4) = 80$이다. ($T_j$ 점수 중 최댓값)
입력으로 기본 트리 ($T_0$)와 $m$번의 "간선 바꾸기"에 대한 정보가 주어졌을 때, Bob을 도와 각 트리의 점수를 구해보자. 단, Alice는 Bob의 편의를 위해 총 $3$개의 값만 구해보라고 했다: $T_0$의 점수, $1$~$m$번째 변형트리 ($T_1$, $\dots$, $T_m$) 점수들의 최솟값과 최댓값을 구하면 된다.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $n$과 $m$이 공백으로 구분되어 주어진다. 다음 $n-1$줄에 걸쳐 $T_0$의 간선에 대한 정보가 $1$번 간선부터 $n-1$번 간선까지, 각 줄에 $3$개의 정수로 나뉘어 주어진다: 처음 $2$개의 정수는 노드 번호이고 세 번째 정수는 간선의 길이이다. 다음 $m$줄에 걸쳐 각 줄에 $4$개의 정수가 주어진다: Alice가 적용할 $j$번째 "간선 바꾸기"에 사용될 $A[ j ]$, $x[ j ]$, $y[ j ]$, $z[ j ]$ 값이 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
각 줄에는 세 개의 정수가 공백으로 구분되어 출력되어야 한다. 첫 정수는 기본 트리 $T_0$의 점수, 두 번째 정수는 $1$~$m$번째 변형 트리 ($T_1$, $\dots$, $T_m$) 점수 중 최솟값, 그리고 세 번째 정수는 $1$~$m$ 번째 변형 트리 ($T_1$, $\dots$, $T_m$) 점수 중 최댓값을 출력한다.
제한
각 테스트 케이스에 대하여:
- $1 ≤ A[ j ] ≤ n - 1$ ($j = 1, 2, \dots, m$)
- $1 ≤ x[ j ] , y[ j ] ≤ n$ 그리고 $x[ j ] \ne y[ j ]$ ($j = 1, 2, \dots, m$)
- $1 ≤ z [ j] ≤ 20\, 000$ ($j = 1, 2, \dots, m$)
- $T$, $n$, $m$에 대한 제한은 서브태스크를 참고한다.
- 서브태스크 중 일부는 입력으로 주어지는 기본 트리의 지름에 대한 제한이 있다.
트리의 "지름 (diameter)"을 다음과 같이 정의한다: 트리의 임의의 두 노드 $x$, $y$를 잇는 최단경로를 $P(x, y)$라 하고, 이에 속한 간선의 개수를 $C(x, y)$라 하자. 트리의 지름은 $C(x, y)$ 값들 중 최댓값이다.
서브태스크 1 (10점)
- $1 ≤ T ≤ 10$
- $2 ≤ n ≤ 1\,000$
- $1 ≤ m ≤ 500$
- $1 ≤ T_0$ 의 지름 $≤ 200$
서브태스크 2 (20점)
- $1 ≤ T ≤ 10$
- $2 ≤ n ≤ 50\,000$
- $1 ≤ m ≤ 20\,000$
- $1 ≤ T_0$ 의 지름 $≤ 200$
서브태스크 3 (70점)
- $1 ≤ T ≤ 10$
- $2 ≤ n ≤ 50\,000$
- $1 ≤ m ≤ 20\,000$
- $1 ≤ T_0$ 의 지름 $≤ n-1$
예제 입력 1
5 3 4 1 2 10 2 3 20 1 3 1 1 1 1 3 20 2 2 3 30 2 3 1 30 10 1 1 2 2 1 3 2 2 9 3 3 4 3 8 7 2 7 6 3 6 4 4 4 5 4 10 9 4 7 8 10 10 9 2 1 2 3 1 3 2 2 4 2 3 8 1 9 3 2 5 8 3 6 8 2 7 8 3 4 8 2 10 4 4 5 10 7 5 3 4 20 2 5 10 1 5 30 4 5 40 6 7 50 7 1 60 1 3 5 1 1 3 2 1 1 3 7 1 1 3 6 1 1 3 4 1 2 3 1 2 1 1 1 2 2 1 2 1 3 1 1 2 4
예제 출력 1
60 42 80 435 614 614 194 378 432 1840 1566 1886 1 2 4
예제 1: 본문에서 다루었다. 이 트리의 지름은 $2$이다 (최단 경로 중 간선의 개수가 가장 많은 것은 $1$ -- $2$ -- $3$ 이다).
예제 2: 아래 그림은 $T_0$을 나타낸다. 이 트리의 지름은 $8$이다 (최단 경로 중 간선의 개수가 가장 많은 것은 $10$ -- $9$ -- $2$ -- $1$ -- $3$ -- $4$ -- $6$ -- $7$ -- $8$ 이다).
이 트리에서 $7$번째로 주어진 간선인 $(6, 4)$를 삭제하고 대신 길이가 $10$인 간선 $(8, 10)$을 추가한 트리 ($T_1$)은 아래와 같다.
$T_0$의 점수는 $435$이고, $T_1$의 점수가 $614$이므로 이 경우 최솟값/최댓값 모두 $614$가 된다.
예제 3, 4: 추가 설명 없음.
예제 5: $T_0$의 점수는 $1$이다. $Score(T_1) = 2$, $Score(T_2) = 3$, $Score(T_3) = 4$ 이므로 최솟값 최댓값은 각각 $2$와 $4$가 된다.
시간 제한
- Java 8: 6 초
- Python 3: 15 초
- PyPy3: 15 초
- Java 8 (OpenJDK): 6 초
- Java 11: 6 초
- Kotlin (JVM): 6 초
- Java 15: 6 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호