lca 썸네일형 리스트형 BOJ 17399 트리의 외심 https://www.acmicpc.net/problem/17399 17399번: 트리의 외심 첫 번째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 이 트리는 1번 정점, 2번 정점, ..., N번 정점으로 구성된다. 두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 X, Y가 www.acmicpc.net 일단 각 쿼리에 대해 트리에서 최소 공통 조상(Lowest Common Ancestor)을 log n에 구할 수 있어야 한다. 알고리즘 두 정점 a와 b에 대해, 두 정점의 가운데에 위치한 정점 x를 찾는다. a와 b 거리가 짝수여야 한다. 그렇지 않으면 가운데에 위치한 정점을 정의할 수 없다. 단계 1에서 찾은 정점 x로부터 정점 c까지의 거리를 구한다. x.. 더보기 이전 1 다음