문제 설명

비밀통로 끝, 왕궁 지하로 들어가는 길을 커다란 돌문이 막고 있었습니다. 사자 얼굴이 새겨진 말하는 문입니다. 캣이 처음 라이언 타운에 몰래 들어갈 때 만났던 문처럼, 이 문도 왕의 혈통만 들여보냅니다.
"왕가의 족보를 모르는 자는 왕가의 피가 아니다! 내가 묻는 두 사자의 가장 가까운 공통 조상을 모두 대 보아라! 크르릉!"
문이 펼쳐 보인 족보에는 사자가 10만 마리 가까이 적혀 있었고, 질문도 끝없이 이어졌습니다.
"족보가 이렇게 깊은데 질문마다 한 세대씩 거슬러 올라가겠다고? 그 방법, 문이 닫히기 전에 끝날지 검증!?"
"질문이 많을수록 미리 준비해 두면 된다냥!"
왕가의 사자에게는 1번부터 n번까지 번호가 있고, 1번은 왕가의 시조입니다. data는 [parents, queries]입니다.
parents는 길이 n인 리스트입니다.parents[i]는 (i+1)번 사자의 부모 번호입니다. 시조인 1번 사자는 부모가 없으므로parents[0]은 0입니다.queries는 질문 리스트입니다. 질문[u, v]는 "u번 사자와 v번 사자의 가장 가까운 공통 조상은 누구인가?"라는 뜻입니다.
사자 x의 조상은 x 자신, x의 부모, 부모의 부모, … 시조까지입니다(자기 자신도 조상으로 칩니다). u와 v의 공통 조상 가운데 시조에서 가장 먼(가장 아래 세대인) 사자가 가장 가까운 공통 조상입니다.
질문마다 가장 가까운 공통 조상의 번호를 구해, 질문 순서대로 담은 리스트를 return 하세요.
제한 사항
- n은 1 이상 100,000 이하입니다.
parents[0]은 0이고, 2번~n번 사자의 부모는 1 이상 n 이하인 다른 사자의 번호입니다. 어느 사자든 부모를 따라 올라가면 1번 사자에 닿습니다(족보는 1번을 뿌리로 하는 트리입니다).- 부모의 번호가 자식의 번호보다 클 수도 있습니다.
- 족보가 한 줄로 길게 이어질 수도 있습니다. 시조에서 가장 먼 사자까지 n-1세대일 수 있습니다.
queries의 길이는 1 이상 100,000 이하이고, u와 v는 1 이상 n 이하의 정수입니다. u와 v가 같을 수도 있습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| [[0, 1, 1, 2, 2, 3, 5], [[4, 7], [7, 6], [2, 5], [3, 3]]] | [2, 1, 2, 3] |
| [[0, 4, 1, 3, 2], [[5, 3], [2, 4], [5, 5]]] | [3, 4, 5] |
| [[0, 6, 1, 6, 3, 1, 4, 4, 2, 3], [[7, 8], [9, 8], [5, 10], [9, 5], [6, 7]]] | [4, 6, 3, 1, 6] |
입출력 설명
입출력 예 #1
1
/ \
2 3
/ \ \
4 5 6
|
7
- 4번의 조상은 4, 2, 1이고 7번의 조상은 7, 5, 2, 1입니다. 공통 조상 2, 1 가운데 가장 아래 세대는 2번입니다.
- 7번과 6번의 공통 조상은 1번뿐입니다.
- 2번은 5번의 부모이므로, 2번과 5번의 가장 가까운 공통 조상은 2번 자신입니다.
- 3번과 3번은 같은 사자이므로 답은 3번입니다.
입출력 예 #2
2번의 부모는 4번, 3번의 부모는 1번, 4번의 부모는 3번, 5번의 부모는 2번이라 족보는 1 - 3 - 4 - 2 - 5로 한 줄입니다. 번호가 크다고 아래 세대인 것은 아닙니다. 답은 차례로 3, 4, 5입니다.
입출력 예 #3
1
/ \
3 6
/ \ / \
5 10 2 4
| / \
9 7 8
7번과 8번은 4번, 9번과 8번은 6번, 5번과 10번은 3번, 9번과 5번은 1번이 가장 가까운 공통 조상입니다. 6번은 7번의 조상이므로 6번과 7번의 답은 6번입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [[0, 1, 1, 2, 2, 3, 5], [[4, 7], [7, 6], [2, 5], [3, 3]]] | [2, 1, 2, 3] |
| 2 | [[0, 4, 1, 3, 2], [[5, 3], [2, 4], [5, 5]]] | [3, 4, 5] |
| 3 | [[0, 6, 1, 6, 3, 1, 4, 4, 2, 3], [[7, 8], [9, 8], [5, 10], [9, 5], [6, 7]]] | [4, 6, 3, 1, 6] |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.