백준 3176번(JAVA)
백준 문제중 11438번 LCA2가 있는데, 트리를 타고 올라갈때 한 칸 씩 올라가는게 아니라 2의N승씩 올라가는 빠른 LCA가 있다. 밑에 문제를 풀 줄 안다면 이번 3176번도 손 쉽게 풀 수있다. 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탐색 문제는 부모를 2의N승 부모를 저장한다. 예를들어 위 그림과 같은 트리가 있다고 가정해보자. 기존에는 바로 위의 부모만 저장했다. 그래서 ..
