[Boj 10838] KOI 2015 - 트리 (LCA, 트리)

https://www.acmicpc.net/problem/10838* 풀이 (LCA, 트리)- 노드의 위치가 계속 바뀌기 때문에 희소 테이블, segment tree를 이용한 LCA구하는 방법은 사용하지 못한다.- 결국 O(N)인 방법을 써야하는데 문제에는 다행이 두 지점의 거리가 멀어봐야 1000이라고 제한을 해서 가능하다.부모를 저장하는 배열, 자신의 부모와의 간선의 색을 저장하는 배열 2개를 생성하고 부모 or 색이 바뀔 때마다 바꿔주면 된다.- 정올 사이트보다 백준 저지의 채점 데이터가 더 빡세다. depth를 매번 저장하는 풀이가 정올에서는 통과되었지만 백준은 시간초과가 떠서 다시 풀었다....

[Boj 10838] KOI 2015 - 트리 (LCA, 트리)에 대한 요약내용입니다.

자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.

원문링크 : [Boj 10838] KOI 2015 - 트리 (LCA, 트리)