Informatica Online Judge

  Lowest Common Ancestor (LCA) [2039 / 07F7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 93   Total Tried : 113


The Champion of this Problem (C++) : gs15044 - ms / 844byte
My Best Submission (C++) : N/A

[koistudy.net (33rd 신승원)]

Background

정점 1을 루트로 하는 트리에서, {x, x의 부모, x의 부모의 부모... } 의 집합을 정점 x의 "조상" 이라고 정의하자. (x는 x의 조상이 아니지만, 여기서는 편의상 조상이라고 한다.) 정점 1은 부모가 없으니. 정점 1의 조상은 {1} 이 유일하다.

또한, x의 "깊이" 를 정점 x와 정점 1의 거리라 정의하자. x의 깊이가 D일때, x의 부모의 깊이는 D-1, x의 부모의 부모의 깊이는 D-2인 관계를 가질 것이다.

이 때, a와 b의 공통 조상 중에서, 깊이가 가장 깊은 (=루트와의 거리가 가장 먼) 노드의 번호를 출력하는 프로그램을 작성하여라.

Input

첫 번째 줄에는 트리의 정점의 갯수 N과 질의의 갯수 Q가 공백으로 구분된 주어진다. (1 ≤ N, Q ≤ 100,000)
두 번째 줄부터 N번째 줄까지는 트리의 간선이 연결하는 두 정점 a와 b의 번호가 주어진다. ( 1 ≤ a,b ≤ N, a≠b )
(N+1)번째 줄부터 (N+Q)번째 줄까지는 정점 a와 b가 주어진다.

Output

입력의 (N+i) ( 1 ≤ i ≤ Q )번째 줄에 대한 질의의 결과값을 i번째 줄에 출력한다.

IO Example

입력
5 4
3 4
5 3
1 2
1 3
2 1
1 4
4 5
2 5

출력
1
1
3
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]