hellogaon

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번째 부모까지의 가..