https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 희소 배열을 이용한 LCA 문제였습니다. 문제는 최소 / 최댓값을 구해야 하는 것입니다. 처음에는 단순히 모든 값을 비교해야 하기 때문에 기본적은 LCA 의 방식으로 하나씩 거슬러 올라갔지만 실패하고 다시 생각해야 했습니다. 희소 배열을 구성할 때 최대, 최솟값을 포함한 배열을 만들면 이 또한 빠르게 구할 수 있게 됩니다. DP 와 비슷한 개념으로 어차피..