33808번 - Binarytreefication 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 53 | 14 | 14 | 32.558% |
문제
$N \le 2\,000$을 만족하는 노드 $N$개의 트리 $T$가 주어진다. 다음의 조건을 만족하는 트리 $T'$를 구성하여 출력하자.
- $T'$의 크기를 $M$이라 하자. $M$은 $N$ 이상 $22\,000$ 이하여야 한다. 즉, $N \le M \le 22\,000$이여야 한다.
- $T'$은 이진 트리이여야 한다. 즉, $T'$의 모든 노드는 $3$개 이하의 다른 노드들과 연결되어야 한다.
- $\text{dist}(u, v)$를 $T$에서 $u$번 노드와 $v$번 노드 사이의 거리로 정의하자. 비슷하게, $T'$에 대해서 $\text{dist}'(u, v)$를 $u$번 노드와 $v$번 노드의 거리로 정의하자.
- $1 \le u, v, p, q \le N$에 대해 $\text{dist}'(u, v) = \text{dist}'(p, q)$이면 $\text{dist}(u, v) = \text{dist}(p, q)$이여야 한다.
입력
첫째 줄에 $N$이 주어진다.
둘째 줄부터 $N-1$개의 줄에 걸쳐 $T$의 각 간선의 양 끝점의 번호가 한 줄에 공백으로 구분되어 주어진다.
출력
첫째 줄에 $M$을 출력한다.
둘째 줄부터 $M-1$개의 줄에 걸쳐 $T'$의 각 간선의 양 끝점의 번호를 한 줄에 공백으로 구분하여 출력한다.
제한
- $2 \le N \le 2\,000$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $N \le 10$ |
| 2 | 8 | $N \le 20$ |
| 3 | 11 | $N \le 100$ |
| 4 | 22 | $N \le 1\,000$ |
| 5 | 55 | 추가적인 제약 조건이 없다. |
예제 입력 1
6 1 2 2 3 3 4 3 5 3 6
예제 출력 1
10 4 1 1 7 7 2 2 8 8 3 3 9 9 5 3 10 10 6
노트
트리는 임의의 두 정점 사이의 단순 경로가 유일하게 존재하는 연결 그래프를 말한다.
출처
University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest H번
- 문제를 만든 사람: mingyu331
- 문제를 검수한 사람: ainta, ibm2006, koosaga, moonrabbit2
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호