트리에서 두 원소의 가장 가까운 공통 조상을 찾는 문제입니다. 제가 한게 맞는지는 모르겠지만 제 방법은 다음과 같습니다. 먼저 주어진 입력으로 트리를 구성합니다. 1을 큐에 넣고 방문하지 않은 노드(결국에는 자식 노드가 됩니다)를 계속 찾아 부모-자식 관계를 찾습니다. 그리고 이 과정에서 각 노드의 깊이와 부모 노드의 번호를 저장합니다. 이제 두 노드에 대한 입력을 받습니다. 두 노드의 깊이가 다르면 저장해놓은 부모 노드의 번호를 사용해서 둘 중 얕은 깊이로 이동합니다. 이제 두 값이 같아질 때까지 한 칸 씩 부모 노드를 찾아갑니다. 두 값이 같아진다면 그 노드가 두 노드의 가장 가까운 공통 조상이 될 것입니다.
PS알못 OrbitHv의 PS