문제
루트가 있는 트리는 컴퓨터 과학이나 엔지니어링에서 잘 알려진 자료구조이다.
예를 들면 다음과 같다.
위 그림에서 각각의 노드는 {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개의 서로 다른 정수가 주어지는데 가장 가까운 공통 조상을 알고 싶은 두 개의 노드이다.
노드 번호는 1 ~ N 범위이다.
출력
두 개의 노드에 대한 가장 가까운 공통 조상의 번호를 출력한다.
예제1
입력
16
114
85
1016
59
46
84
410
113
615
1011
67
102
163
81
1612
167
출력
4
출처
Taejon 2002,poj1330