6145 : 트리 높이·크기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리의 전체 노드 수 N과 루트 노드 R, 그리고 간선 정보가 주어질 때, 트리의 전체 높이와 각 노드를 루트로 하는 서브트리의 크기(노드 개수)를 구하시오.
트리의 높이는 루트로부터 가장 먼 리프 노드까지의 간선 수로 정의하며, 단일 노드일 경우 높이는 0입니다.
트리의 높이는 루트로부터 가장 먼 리프 노드까지의 간선 수로 정의하며, 단일 노드일 경우 높이는 0입니다.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)과 루트 노드의 번호 R (1 ≤ R ≤ N)이 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 u, v가 주어집니다.
둘째 줄부터 N-1개의 줄에 u, v가 주어집니다.
출력 설명
첫째 줄에 트리의 전체 높이를 출력합니다.
둘째 줄에 1번 노드부터 N번 노드까지 각 노드를 루트로 하는 서브트리의 크기를 공백으로 구분하여 출력합니다.
둘째 줄에 1번 노드부터 N번 노드까지 각 노드를 루트로 하는 서브트리의 크기를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 1
1 2
1 3
3 4
3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
5 1 3 1 1