[Boj 13309] KOI 2016 - 트리<high> (LCA, 세그먼트 트리, Lazy Propagation)

https://www.acmicpc.net/problem/13309* 풀이 (LCA, 세그먼트 트리, Lazy Propagation)- 노드 b, c가 lca(b, c)까지 가각 단절선이 없다면 노드 b에서 c로가는 경로는 존재하지 않는다.i) 노드 X와 X의 조상 노드 Y가 있을 때, 노드 X와 노드 Y사이에 단절선이 있는지 어떻게 아는가?모든 노드가 자신위에 존재하는 단절선의 개수를 알고 있다면 가능하다.아래 그림을 보자4와 3이 연결되었는지 알고 싶다.lca(4, 3)은 1이다.4위로의 단절선 개수는 11위로의 단절선 개수는 03위로의 단절선 개수는 0cutCnt(x)를 노드 x위에 존재하는 단절선 개수를 알아내는 함수라고 하자cutCnt(4) - cutCnt(1) = 1 이므로, 4와 1사이에..........

원문링크 : [Boj 13309] KOI 2016 - 트리<high> (LCA, 세그먼트 트리, Lazy Propagation)