BOJ 28244 - 사람이 먼저 되라

BOJ 28244 - 사람이 먼저 되라

센트로이드 트리를 씀이 자명하다.

기본문제와 크게 다르지 않고 <가중치 합, 가중치 최대값> 을 관리하며

모든 자식 노드들마다 하나씩 이 값들을 세그먼트 트리에서 지워주고 세그먼트 트리에 남은 부분들에서 가중치 최댓값보다 작은 부분들의 합과 그 개수들을 쿼리해주는 식으로 정답에 올바르게 더해줄 수 있다.

가중치 합이 같은 경우는 따로 쿼리하여 $2$를 나눠주거나 하면 된다.

처음엔 다이나믹 세그먼트 트리로 겨우 4700ms에 통과했으나 펜윅으로 좌표압축 후 고치고나서 1800ms로 여유롭게 통과할 수 있었다.