https://www.acmicpc.net/problem/15480
15480번: LCA와 쿼리
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(
www.acmicpc.net
엄밀한 증명은 잘 모르겠고, 루트가 1인 트리를 상상하고 u와 v의 lca 경로를 그린 다음 트리 상에서 r을 여러 개 잡아서 생각해 보았다. r에서 간선을 잘 따라가서 이 경로와 만나는 지점을 찾으면 됨을 알 수 있었다. 다양한 개형을 생각해 본 결과 lca(r, u), lca(r,v), lca(u,v)중 두 값이 같으면 나머지 한 값이 원하는 답이 됨을 확인할 수 있었다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 23911 Beauty of tree (0) | 2023.02.16 |
|---|---|
| 백준 4792 레드 블루 스패닝 트리 (0) | 2023.02.15 |
| 백준 1772 정원 정리 (0) | 2023.02.09 |
| 백준 6181 플러드 필 (Flood Fill) (0) | 2023.02.07 |
| 백준 11873 최대 직사각형 (1) | 2023.02.04 |
