| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 173 | 70 | 63 | 54.310% |
트리 문제만 공부하다 정신이 돌아버린 형진이는, 트리를 뽀개기로 결정하였다.
여기 $N$개의 정점으로 이루어진, 간선에 가중치가 있는 트리가 있다. 이 트리는 항상 1번 노드가 트리의 루트가 된다.
형진이는 슈퍼 트리 뽀개기를 1회 사용하여 이 트리를 뽀갤 수 있다. 트리의 특정 노드를 하나 선택한 후, 그 노드부터 거리가 $K$ 이하에 있는 손자 노드 모두를 뽀개버린다.
노드 사이의 거리는 다음과 같이 정의된다.
손자 노드는 다음과 같이 정의된다.
다음은 $K$ = 2일 때 트리를 뽀개는 예시이다. 왼쪽의 경우 1번 노드를 선택해 슈퍼 트리 뽀개기를 진행했고, 오른쪽의 경우 3번 노드를 선택해 슈퍼 트리 뽀개기를 진행했다. 각각 4, 5개의 노드가 뽀개졌다.
형진이는 최대한 많은 노드를 뽀개고 싶다. 형진이를 도와 최대한 많은 노드를 뽀갰을 때 몇 개의 노드를 뽀갤 수 있는지 구해보자.
입력은 다음과 같이 주어진다.
$N$ $K$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\cdots$
$a_{N-1}$ $b_{N-1}$ $c_{N-1}$
첫째 줄에 트리 노드의 개수 $N,ドル 뽀갤 수 있는 손자 노드의 거리 $K$가 공백을 사이에 두고 주어진다.
두 번째 줄부터 $N - 1$개의 줄에 걸쳐 간선에 연결된 두 노드의 번호 $a_i,ドル $b_i,ドル 그리고 해당 간선의 가중치 $c_i$가 공백을 사이에 두고 주어진다.
슈퍼 트리 뽀개기를 통해 최대한 많은 노드를 뽀갤 때 몇 개의 노드를 뽀갤 수 있는지 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | 모든 1ドル \leq i \leq N$에 대해 $c_i$ = 1이다. |
| 2 | 70 | 추가적인 제약 조건이 없다. |
10 2 1 2 1 1 3 1 2 4 1 3 5 1 4 6 1 5 7 1 5 8 1 5 9 1 5 10 1
6
10 2 1 2 1 1 3 1 2 4 2 3 5 1 4 6 1 5 7 1 5 8 1 5 9 1 5 10 3
5
University > 연세대학교 > 2023 연세대학교 프로그래밍 경진대회 G번