ACM 예선에서 트리에서의 두 정점간의 최단거리를 구하는 방법을 몰라서 충격받고 바로 그 방법인 LCA를 공부했다. 공부하고보니 그렇게 어려운 알고리즘도 아니어서 더욱 아까웠다.LCA 알고리즘은 말 그대로 트리에서 두 정점간의 가장 깊은(루트에서 먼) 부모 노드를 찾아내는 알고리즘이다. 그 부모 노드를 찾으면 거리 또한 자연스럽게 알아낼 수 있다. 일단 naive하게 두 노드가 서로 만날 때까지 위로 한칸 한칸씩만 올라가면, 트리가 일직선으로 쭉 뻗어있는 모형에서 시간이 O(N)이 소요된다(트리의 노드의 개수가 N개). 따라서 11438-LCA2 같이 노드가 10만개, query가 10만개가 들어올 경우 시간이 터지게 된다. 따라서 O(N)보다 더 빠르게 찾아내야 하는데 실제로 O(logN)만에 가능하다..
1761-정점들의 거리(LCA) 가중치가 주어진 트리에서의 최단거리를 구하는 알고리즘이다. 물론 트리도 그래프의 일종이므로 최단거리 알고리즘인 다익스트라나 SPFA알고리즘을 사용할 수 있겠으나, 이 문제는 쿼리가 많이 들어오기 때문에 트리 전용 최단거리 알고리즘이 필요하다. 그 알고리즘이 바로 LCA알고리즘을 조금만 응용시키면 두 정점사이의 최단거리를 O(logN)만에 구할 수 있다. 참고로 이 알고리즘은 오직 트리에서만 가능한데, 특별히 이 알고리즘이 더 빠른 이유는 트리의 특징중에 하나인 노드~노드로 갈 수 있는 경로가 unique하기 때문이다.LCA알고리즘을 어떻게 응용하느냐가 관건이다. 뭐 복잡하지도 않고 단순히 생각해보면 정점 A~B의 최단거리를 구하려면 dist(A~LCA(A,B)+dist(B..