| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 346 | 163 | 131 | 44.863% |
1ドル$번부터 $N$번까지 번호가 부여된 $N$개의 정점을 $N-1$개의 간선으로 연결하여 트리를 만들고자 한다. 이때, 모든 정점의 차수가 $K$ 이하가 되도록 하면서 지름이 최소가 되는 트리를 아무거나 하나 출력해 보자.
트리의 지름이란, 트리에서 임의의 두 정점 사이의 거리 중 가장 먼 거리를 의미한다.
첫째 줄에 정수 $N,ドル $K$가 공백을 사이에 두고 주어진다. $(2 \le K < N \le 300,000円)$
$N-1$개의 줄에 걸쳐 $i$번째 간선이 연결하는 두 정점의 번호를 공백으로 구분하여 출력한다.
8 3
8 1 1 6 2 1 2 5 4 5 7 2 7 3
위 그림에서 $(8, ,円 1, ,円 2, ,円 7, ,円 3)$과 같은 경로를 보면, 정점 8ドル$과 3ドル$의 거리가 트리의 지름이 된다. 이는 트리에서 가장 먼 두 정점을 연결하는 경로 중 하나이다.
이때 $N=8 , ,円 K=3$인 조건을 만족하는 트리 중, 지름이 4ドル$로 최소이다.
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 10. C번