가까운 공통 조상 찾기 > 문제은행

fff

1440 : 가까운 공통 조상 찾기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
208 회   
시도횟수
734 회   

문제

루트가 있는 트리는 컴퓨터 과학이나 엔지니어링에서 잘 알려진 자료구조이다. 예를 들면 다음과 같다.

 


 

위 그림에서 각각의 노드는 {1,2,...,16}의 라벨을 1개씩 가지고 있다. 8번 노드는 루트이다. 만약 노드 x가 루트에서부터 노드 y까지의 경로(path) 상에 나타나면 x는 노드 y의 조상이 된다. 이를 테면 노드 4는 노드 16의 조상입니다. 노드 10 역시 노드 16의 조상이다.

노드 x가 서로 다른 노드 y와 z의 조상이면 x를 y와 z의 공통 조상이라고 부른다. 이러한 공통 조상들 중에 y와 z에 가장 가까운 공통 조상을 가장 가까운 공통 조상이라고 칭한다. 따라서 2와 3의 가장 가까운 공통 조상은 10이 된다. 만약 y가 z의 조상이라면 y가 가장 가까운 공통 조상이 된다.

트리 내에서 두 개의 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하라.


입력형식

첫 줄에 노드의 수 N 2≤N≤10,000 이 주어지고 N-1줄에 걸쳐 두 개의 정수가 주어진다. 두 수 중 첫 번째 수가 두 번째 수의 부모 노드가 된다. 다음으로 2개의 서로 다른 정수가 주어지는데 가장 가까운 공통 조상을 알고 싶은 두 개의 노드이다.

출력형식

두 개의 노드에 대한 가장 가까운 공통 조상의 번호를 출력한다.

입력 예

16 
1 14 
8 5 
10 16 
5 9 
4 6 
8 4 
4 10 
1 13 
6 15 
10 11 
6 7 
10 2 
16 3 
8 1 
16 12 
16 7

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP