[BOJ] 백준 14268 내리 갈굼 2

문제 링크

트리의 한 노드가 갈굼당하면 그 자식들이 모두 갈굼당해야한다. 구간이 보인다. 트리를 평평하게 펴서 세그먼트 트리로 만들고, lazy propagation을 적용하자.

비슷한 문제로 15782 Calculate! 2 가 있다. 트리를 펴는 자세한 설명은 해당 링크를 보자.

위 링크와 차이점은 이번에는 pre-order로 순회했다는 것이다. 

두 배열 $l$과 $r$, 주어진 트리의 어떤 정점 x에 대해 $l[x]$는 세그먼트 트리에서 x의 시작 구간이고 $r[x]$는 끝 구간이다.

이를 dfs로 쉽게 구할 수 있다.

$l[x]$는 순회하는 순서로 값을 채워넣으면 된다.

$r[x]$는 모든 자식들을 순회한 뒤 $l[x]$에서 자식 수만큼 증가시켜 넣어준다. (이는 세그먼트 트리에서 x의 마지막 자식의 위치이다)

또한 쿼리에 답할 때, 구간에 대해 묻는 게 아니라 한 정점에 대해 묻는 것이므로 구간 i, j를 받지 않고 정점 위치 idx만 받는다. 그냥 i, j 쿼리를 구현해서 같은 값을 넣어줘도 된다.

정답 코드

질문 및 피드백 환영합니다.