Page not loading? Try clicking here.
Placeholder

#8683
Subtask

두더지굴 1s 1024MB

Problems

지하에 N개의 방이 있는 두더지굴이 있다. 각 방은 1번부터 N번까지 서로 다른 번호가 붙어 있고, 서로 다른 두 개의 방을 잇는 굴이 N-1개 존재한다. 또한, 임의의 한 방에서 다른 방으로 하나 이상의 굴을 통하여 이동할 수 있음이 보장된다.

처음에 i번 방에 A_i 마리의 두더지가 살고 있다. 모든 방의 두더지의 마리 수는 총 (N), (N+1), (N+2) 중 하나의 값이라는 것이 보장된다.

한 방에 너무 많은 두더지가 몰려있으면 지반이 무너질 수 있기에 모든 방의 두더지 수는 최소 한 마리에서 최대 두 마리까지만 위치해 있어야 한다. 두더지들은 굴을 따라 다른 방으로 자유롭게 이동이 가능한데, 각 두더지가 이동한 거리는 거쳐간 굴의 개수로 정의된다.

지반을 안정화하기 위한 최소 이동 거리의 총합을 구하는 프로그램을 작성하시오.


Input

첫 줄에 방의 개수를 의미하는 정수 N이 주어진다.

두 번째 줄에 A_1, A_2, \cdots, A_N이 공백으로 구분되어 주어진다.

이어 N-1 줄에 걸쳐 각 굴이 직접적으로 연결하는 두 방의 번호가 주어진다.

[제약 조건]

  • 2 \le N \le 500\ 000

  • A_i \ge 0

  • N \le \sum\limits_{i=1}^N{A_i} \le N+2


Output

첫 줄에 지반을 안정화하기 위한 최소 이동 거리의 총합을 출력한다.


Subtask

# Score Condition
#117

i번째 굴은 i번 방과 i+1번 방을 연결한다. (1 \le i \le N-1)

#29

N \le 500

#315

N \le 5\ 000

#419

\sum\limits_{i=1}^N{A_i} = N

#523

\sum\limits_{i=1}^N{A_i} = N+1

#617

추가 제약 조건 없음


Example #1

5
0 1 2 0 2
1 2
1 3
2 4
2 5
3

Example #2

5
0 0 2 4 1
1 2
2 3
3 4
4 5
5


Source

New York Programming Contest 2025

You must sign in to write code.