MathTrauma

문제 링크 : 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 최소 공통 조상을 \(\log(n)\) 시간 이내로 찾을 수 있도록 해주는 것은 이중 배열 prv 이다. 이 배열은 음이 아닌 정수 k 에 대해 \(2^k\) 만큼 앞의 선조에 대한 정보를 기록하고 있다. prv[i][k] 는 i 번 노드의 \(2^k\) 번째 선조로 prv[i][k]=prv[prv[i][k-1]][k-1] 을 만족한다. 도..