문제
정원이는 세계1등 OTT서비스인 정올TV에서 TV 프로그램을 시청하는 것을 좋아한다.
그리고 그녀는 여러 다른 장소에서 그것들을 시청한다.
정원이는 대저택에 살고 있는데, 정원이의 집에는 총 N개의 방이 있고, 이는 노드 수가 N인 트리로 나타낼 수도 있다.
대저택 안에는 정원이가 정올TV를 시청하는 방이 정해져 있는데, 적어도 하나의 방에서는 정원이가 정올TV를 시청한다는 것이 보장된다.
불행히도, 정올TV는 비밀번호 공유를 방지하기 위해 새로운 구독 모델을 도입하고 있다.
이 새로운 모델에서는 d개의 연결된 인접한 방들을 선택하면 해당 연결된 방들에서 사용할 수 있는 계정을 1개월 동안 d+k 달러를 지불하여 사용해야 한다.
정원이는 계정을 한 개 혹은 여러 개 만들어서 사용 할 수 있는데, 이 때 정올TV를 시청하는 모든 방들은 반드시 계정 등록이 되어야한다.
C개의 계정을 만들어서 각 계정에 포함되는 방들의 집합 c1,c2,…,cC를 선택한다면, 총 계정 구독 비용은
이며, 여기서 |ci|는 계정 ci에 등록된 방의 수를 뜻한다.
정원이가 정올TV를 시청하지 않는 방들은 계정 등록이 되지 않아도 된다.
정원이는 새로운 구독 모델이 너무 비싸지 않을까 걱정하며, 한컴TV로 전환하려고 고민하고 있다.
그녀의 의사 결정을 돕기 위해 정올TV에 지불해야 할 최소 금액을 계산해야 한다.
정올TV는 k의 값을 발표하지 않았으므로, k가 1에서 N까지의 모든 정수 값인 경우 하나하나에 대해 모두 계산해야 한다.
입력
첫 번째 줄에 N을 입력받는다. (2≤N≤2⋅105)
두 번째 줄에 s1s2s3… sN을 의미하는 비트문자열을 입력받는다.
이때, si =1이라면 방i는 정원이가 정올TV를 시청하는 방이다.
그 다음 N-1줄에 걸쳐 두 정수 a와 b가 입력되는데, a와 b는 트리에서 서로 연결된 방들을 의미한다. (1≤a,b≤N)
출력
1부터 N까지의 각 k에 대한 답을 각 줄에 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | N ≤ 5000 |
| #2 | 80점 | 추가 제한 조건 없음 |
예제 #1
5
10001
1 2
2 3
3 4
4 5
4
6
8
9
10
예제 #2
7
0001010
7 4
5 6
7 2
5 1
6 3
2 5
4
6
8
9
10
11
12
로그인해야 코드를 작성할 수 있어요.