11437

문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 최소 공통 조상을 찾는 문제입니다. 위 문제는 sparse table이나 세그먼트 트리를 사용하지 않고, dfs로도 구현이 가능합니다. 우선 입력 값을 Arraylist[] 배열에 넣어 트리 상의 연결된 두 정점을 표현합니다. 그리고 parents[] 배열과 depth[] 배열을 통해 각 정점의 부모와 깊이를 저장합니다. (findDepthAndParents 메서드) 그럼 pare..