6161 : 센트로이드 분해 기초
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
노드의 개수가 N인 트리에서 센트로이드 분해(Centroid Decomposition)를 적용했을 때, 각 노드의 센트로이드 트리 상의 부모 노드 번호를 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v가 주어집니다.
출력 설명
1번 노드부터 N번 노드까지 각 노드가 센트로이드 트리 상에서 갖는 부모 노드 번호를 공백으로 구분하여 한 줄에 출력합니다. 루트 센트로이드의 부모는 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2
1 3
1 4
1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1 0 0 0 0