문제
$1$번부터 $N$번까지 번호가 부여된 $N$개의 정점을 $N-1$개의 간선으로 연결하여 트리를 만들고자 한다. 이때, 모든 정점의 차수가 $K$ 이하가 되도록 하면서 지름이 최소가 되는 트리를 아무거나 하나 출력해 보자.
트리의 지름이란, 트리에서 임의의 두 정점 사이의 거리 중 가장 먼 거리를 의미한다.
입력
첫째 줄에 정수 $N$, $K$가 공백을 사이에 두고 주어진다. $(2 \le K < N \le 300\,000)$
출력
$N-1$개의 줄에 걸쳐 $i$번째 간선이 연결하는 두 정점의 번호를 공백으로 구분하여 출력한다.
예제 입력 1
8 3
예제 출력 1
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번
- 문제를 만든 사람: moonlit
- 문제를 검수한 사람: bnb2011, chogahui05, heeda0528, kiwiyou, kongum, nflight11, pjshwa, snrnsidy, utilforever