3176번: 도로 네트워크

3176번: 도로 네트워크 - LCA

간선에 가중치가 있는 트리가 주어질 때 정점 u에서 정점 v까지의 경로의 간선들 중

가장 작은 가중치, 가장 큰 가중치를 출력하는 문제이다.

100,000개의 쿼리를 처리해야하기에 효율적인 방법이 필요한데

경로가 유일하다는 것을 이용하여 LCA를 이용해보자

u, v의 경로는 u - LCA(u,v) - v 로 이루어져 있기 때문이다.

그렇다면 LCA를 구하면서 가장 작은 가중치, 가장 큰 가중치를 구할 수 있을까?

LCA에서는 정점의 2^k번째 부모를 저장해놓는다.

즉 한 정점의 2^(k+1)번째 부모는 그 정점의 2^k번째 부모의 2^k번째 부모와 같다를 이용하였다.

이와 비슷하게 한 정점의 2^(k+1)번째 부모까지의 가장 작은 가중치는

min(그 정점의 2^k번째 부모까지의 가장 작은 가중치, 그 정점의 2^k번째 부모에서 2^k번째 부모까지의 가장 작은 가중치)

로 표현 할 수 있고 이는 LCA 알고리즘과 비슷한 방법으로 문제를 풀어나갈 수 있다.

가장 큰 가중치 또한 위의 방법으로 구현하여 출력해주면 풀 수 있는 문제이다.