BOJ 15480 - LCA와 쿼리

Joonas' Note

BOJ 15480 - LCA와 쿼리 본문

알고리즘/문제 풀이

BOJ 15480 - LCA와 쿼리

2020. 5. 15. 20:00 joonas 읽는데 2분
  • 문제
  • 코드

링크: https://www.acmicpc.net/problem/15480

문제

문제 설명은 간단하다.

루트를 r로 하는 트리에서 u와 v의 최소공통조상(LCA)를 출력하는 문제이다.


LCA(r, u), LCA(r, v), LCA(u, v) 세 개 중에서 깊이가 더 깊은 노드를 출력하면 된다.

증명은 사실 안 했는데, 케이스 몇 개를 두고 해보니까 계속 답이었다..

혹시나 싶어서 제출해봤더니 정답

코드