hjhj97

1761-정점들의 거리(LCA) 가중치가 주어진 트리에서의 최단거리를 구하는 알고리즘이다. 물론 트리도 그래프의 일종이므로 최단거리 알고리즘인 다익스트라나 SPFA알고리즘을 사용할 수 있겠으나, 이 문제는 쿼리가 많이 들어오기 때문에 트리 전용 최단거리 알고리즘이 필요하다. 그 알고리즘이 바로 LCA알고리즘을 조금만 응용시키면 두 정점사이의 최단거리를 O(logN)만에 구할 수 있다. 참고로 이 알고리즘은 오직 트리에서만 가능한데, 특별히 이 알고리즘이 더 빠른 이유는 트리의 특징중에 하나인 노드~노드로 갈 수 있는 경로가 unique하기 때문이다.LCA알고리즘을 어떻게 응용하느냐가 관건이다. 뭐 복잡하지도 않고 단순히 생각해보면 정점 A~B의 최단거리를 구하려면 dist(A~LCA(A,B)+dist(B..