페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#9659

트리 순회 1s 256MB

문제

루트 노드를 1로 하고 노드 개수가 N개인 트리가 주어진다.

특정 노드에 대해 아래 4가지 정보를 구해야 하는 프로그램을 작성하자.

  1) 루트와의 거리

  2) 본인 포함 자손노드 개수

  3) 가장 먼 자손노드와의 거리​

  4) 가장 먼 노드와의 거리 


입력

첫째 줄에 노드 개수 N이 주어진다.

둘째 줄부터 N-1개 줄에 걸쳐 두개의 정수 cid, pid 가 주어진다.

cid는 자식노드, pid는 부모노드를 의미한다.

마지막 줄에는 검색의 기준이 되는 특정 노드 x가 주어진다.

  • 2 \le N \le 1,000

  • 1 \le cid, pid, x \le 1,000


출력

네개 줄에 걸쳐 아래에서 요구하는 결과를 순서대로 출력한다.

  1) 루트와의 거리

  2) 본인 포함 자손노드 개수

  3) 가장 먼 자손노드와의 거리​

  4) 가장 먼 노드와의 거리


예제 

10

2 1

3 1

5 2

6 5

4 5

7 4

8 3

9 3

10 9

3
1

4

2

5

1) 루트와의 거리 3->1 = 1

2) 본인 포함 자손노드 개수 3,8,9,10 = 4

3) 가장 먼 자손노드와의 거리 3->9->10 = 2

4) 가장 먼 노드와의 거리 3->1->2->5->4->7 = 5



출처

teriusu
로그인해야 코드를 작성할 수 있어요.