카우플릭스 시청

*참고: 이 문제의 시간 제한은 기본의 1.5배인 3초이다.*

베시는 카우플릭스(Cowflix)에서 쇼를 시청하는 것을 좋아하며, 여러 다른 장소에서 시청한다. 농부 존의 농장은 \(N\) (\(2 \leq N \leq 2\cdot 10^5\))개의 정점을 가진 트리로 나타낼 수 있으며, 각 정점에서 베시가 카우플릭스를 시청하거나 시청하지 않는다. 베시는 적어도 하나의 정점에서 카우플릭스를 시청하는 것이 보장된다.

안타깝게도, 카우플릭스는 비밀번호 공유에 대응하기 위해 새로운 구독 모델을 도입한다. 새 모델에서는 농장에서 크기 \(d\)의 연결된 컴포넌트를 선택할 수 있으며, 그 연결된 컴포넌트에서 사용할 수 있는 계정에 대해 \(d + k\) 무니를 지불해야 한다. 형식적으로, 서로소인 연결된 컴포넌트들의 집합 \(c_1, c_2, \dots, c_C\)를 선택하여, 베시가 카우플릭스를 시청하는 모든 정점이 어떤 \(c_i\)에 포함되도록 해야 한다. 컴포넌트 집합의 비용은 \(\sum_{i=1}^{C} (|c_i|+k)\)이며, 여기서 \(|c_i|\)는 컴포넌트 \(c_i\)의 정점 개수이다. 베시가 카우플릭스를 시청하지 않는 정점은 어떤 \(c_i\)에도 속할 필요가 없다.

베시는 자신이 방문하는 모든 장소를 고려할 때 새 구독 모델이 너무 비쌀까 걱정되어 무루(Mooloo)로 갈아탈지 고민하고 있다. 그녀의 의사 결정을 돕기 위해, 시청 습관을 유지하기 위해 카우플릭스에 지불해야 하는 최소 금액을 계산하라. 카우플릭스가 \(k\)의 값을 발표하지 않았으므로, \(1\)부터 \(N\)까지의 모든 정수 \(k\)에 대해 계산하라.

출제자: Danny Mittal

배점

• 입력 3-5: \(N\le 5000\)
• 입력 6-8: 모든 \(i\in [1,N)\)에 대해 \(i\)는 \(i+1\)과 연결되어 있다.
• 입력 9-19: \(N\le 10^5\)
• 입력 20-24: 추가 제약 조건이 없다.

출제자: Danny Mittal

첫째 줄에 \(N\)이 주어진다.

둘째 줄에 비트 문자열 \(s_1s_2s_3 \dots s_N\)이 주어지며, 베시가 정점 \(i\)에서 카우플릭스를 시청하면 \(s_i = 1\)이다.

다음 \(N-1\)개의 줄에는 각각 두 정수 \(a\)와 \(b\) (\(1 \leq a, b \leq N\))가 주어지며, 이는 트리에서 \(a\)와 \(b\) 사이의 간선을 나타낸다.

\(1\)부터 \(N\)까지의 각 \(k\)에 대한 답을 각 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > February > Platinum