LCA1
N개의 정점으로 이루어진 트리가 주어진다. 루트 노드는 항상 1번 노드이다.
이때 두 노드 u, v가 주어졌을 때, 두 노드의 가장 가까운 공통 조상(Lowest Common Ancestor, LCA)을 찾는 프로그램을 작성하시오.
가장 가까운 공통 조상이란, 두 노드 u, v를 하위 노드로 가지는 노드들 중에서 가장 깊이가 깊은 노드를 의미한다.
입력
첫째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N-1개의 줄에는 트리의 연결 상태를 나타내는 두 정수 u, v가 공백을 사이에 두고 주어진다.
이는 u번 노드와 v번 노드가 연결되어 있음을 의미한다.
그다음 줄에는 질문의 개수 Q가 주어진다. (1 ≤ Q ≤ 10,000)
다음 Q개의 줄에 걸쳐 가장 가까운 공통 조상을 구해야 하는 두 노드 u, v가 공백을 사이에 두고 주어진다.
출력
Q개의 줄에 걸쳐, 각 질문마다 입력으로 주어진 두 노드의 LCA 노드 번호를 출력한다.
제약 조건
1 ≤ N ≤ 100,000
1 ≤ Q ≤ 10,000
루트 노드는 1번이다.
모든 노드는 연결되어 있는 트리 구조임이 보장된다.
예제 입력 1
15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
3
8 11
12 15
4 5예제 출력 1
2
3
2
코멘트
3가지
0)루트부터의 거리 dis[i]= a
dis[a] + dis[b] - dis[lca(a,b)]*2
1) 깊이 depth[i]= a 루트부터 i노드까지의 깊이가 a이다. detph[i] = detph[부모]+1 2) 서브트리 sub[i]=1 sub[i] = 모든자식 sub 합
sub[x] = 1 for(i:graph[cur]) {
}
결정되는게 == base
3) 부모 p[i]=a
p[i]=