BOJ 24272 - 루트 노드가 많은 트리일수록 좋은 트리이다

June 17, 2023

$u \to v$ 라면 $v$ 쪽에 있는 모든 노드들은 불가능해진다.

오일러 투어 테크닉을 쓰면 $v$ 쪽에 있는 모든 노드들에 불가능한 노드라는 의미로써 $+1$ 을 해줄 수 있다.

$v$ 가 $u$ 의 자식이라면 그냥 $in_u \sim out_u$ 에 해주면 되고 그렇지 않다면 $0 \sim in_u-1$ 와 $out_u+1 \sim n-1$ 에 해주면 된다.

이거 구현 은근 어려운데 왜이리 정답률이 높은지 모르겠다.

이제 0-1 Segment Tree 를 써서 각 쿼리마다 $0$ 인 구간의 개수를 출력해주면 된다.

왜냐면 $0$ 이라 함은 현재 가능한 노드들만 의미하는 것이 되기 때문이다.

You may also enjoy