BOJ 15743 - New Barns
트리에 새로운 정점을 계속해서 추가해나가며 farthest 정점을 찾는 쿼리를 수행해야 한다.
어떤 정점에서 가장 거리가 먼 정점은 항상 트리의 지름에 해당되는 정점 중 하나가 된다.
또한, 정점을 추가할 때도 현재 트리의 지름에 해당하는 두 정점과 추가된 정점의 거리를 비교하면 트리의 지름에 해당되는 정점이 업데이트 되거나 그대로 있거나 둘 중 하나이다.
처음에 모든 쿼리를 먼저 받아 트리를 구성하고 $LCA$를 구성해 두 정점간의 거리를 $O(\log N)$ 에 구할 수 있게 전처리한다.
새롭게 추가되는 정점을 붙여나가며 쿼리를 처리해나가야 하지만 트리의 특성상 먼저 트리를 구성해놓고 build해나가는 과정에 쿼리를 날려도 이미 있는 정점들에 한해서만 최단거리를 잘 찾기 때문에 문제없다.
이 문제에서 까다로운 점은 연결 트리가 아니고 forest라는 점인데, LCA를 여러개 선언할 필요 없이 하나만 선언해놔도 forest에서도 쿼리가 가능하다.
DSU같은 것으로 현재 트리에서의 지름이 어떤 두 정점인지만 잘 관리해나가면 된다.
Comments