LCA

[BOJ] 3176 | 도로 네트워크

Sparse table로 LCA를 구하면서 조상까지의 최장·최단 도로를 함께 DP로 저장해, 각 쿼리를 O(log N)에 처리합니다.