문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 이전 단계 문제인 LCA 와는 다르게 입력의 크기가 크고 제한 시간이 더 짧다. 따라서 최소 공통 조상 알고리즘을 최적화해야 한다. 최적화는 다이나믹 프로그래밍을 이용한 전처리를 통해 LCA를 찾는 시간 복잡도를 O(log Tree_heigth)으로 줄일 수 있다. 이를 위해 x의 2^k(2의 k승)번째 조상을 parent[x][k]..