레이지1 BOJ 13309 - 트리 (레이지, ett, 트리) https://www.acmicpc.net/problem/13309 트리+세그 공부하게 된 계기 최대 2e5개의 정점을 갖는 루트가 1인 트리가 주어진다. 다음 쿼리를 처리하라 x y 1 : 정점x,y를 잇는 경로가 있다면 "YES"출력 후 x와 x의부모를 잇는 간선 제거 없다면 "NO" 출력 후 y와 y의 부모를 잇는 간선 제거 x y 0 : 정점x,y를 잇는 경로가 있다면 "YES", 없다면 "NO" 출력 정점 u와 p[u]의 간선을 끊는 것을 한 쪽의 색을 칠한다고 생각해보면 다음과 같다. u와 A의 크기가 더 작을 경우 u쪽을 새로 칠하고 p[u]와 B의 크기가 더 작을 경우 p[u]쪽의 색을 새로 칠한다면 amortized log시간에 쿼리를 처리할 수 있다. (점점 색칠할 영역이 반절로 줄어듦.. 2020. 5. 22. 이전 1 다음
