33681번 - 택배 상하차는 힘들어

문제

푸앙국에는 $N$개의 도시와 $N-1$개의 도로가 있고, 각 도로는 두 개의 도시를 연결하고 있다. 도시는 1ドル$번부터 $N$번까지 번호가 매겨져 있고, 각 도시에서는 도로를 이용하여 다른 모든 도시로 이동할 수 있다. 우리는 푸앙국에서 도로와 도로를 지나갈 수 있는 트럭을 이용해 $N$개의 도시에 모두 택배를 배송해야 한다.

1. 각 도시에는 택배를 하나도 넣지 않은 충분한 수의 트럭이 대기하고 있으며, 한 도시에서 트럭에 원하는 만큼 그 도시에 놓인 택배를 넣거나(상차) 트럭에 넣었던 택배를 꺼낼(하차) 수 있다.
2. 택배 1ドル$개를 트럭에 넣을 때마다 상차 횟수가 1ドル$ 증가하며, 택배 1ドル$개를 트럭에서 꺼낼 때마다 하차 횟수가 1ドル$ 증가한다.
3. 푸앙국의 모든 트럭은 구조가 특별해 택배를 넣었던 순서의 반대 순서로만 꺼낼 수 있다.
4. 택배가 목적지에 놓이면 그 택배는 배송이 완료된다.
5. 트럭은 두 도시를 연결하는 도로를 지나갈 수 있지만 여러 대의 트럭이 한 도로를 지나갈 수 없으며, 어떤 트럭에 의해 한 번이라도 사용된 도로는 다시 사용할 수 없다.
6. 어떤 도시에서 하차한 택배를 다른 트럭에 상차하는 경우 넣는 순서를 재조정할 수 있다.

처음에는 모든 택배가 1ドル$번 도시에 놓여 있다. 목적지가 1ドル$번 도시인 택배는 이미 배송이 완료된 상태임에 유의해야 한다.

모든 택배를 목적지에 보낼 때 필요한 상차 횟수와 하차 횟수의 합의 최솟값을 출력하자.

입력

첫 번째 줄에 도시의 개수 $N$이 주어진다.

두 번째 줄에 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. $a_i$는 $i$번 도시를 목적지로 하는 택배의 개수이다.

그다음 줄부터 $N-1$개의 줄에 걸쳐 두 개의 도시를 연결하는 도로 정보 $i, j$가 한 줄에 하나씩 주어진다. 이는 $i$번 도시와 $j$번 도시가 도로로 연결되어 있다는 의미이다.

출력

첫 번째 줄에 모든 택배의 배송을 완료한 후 필요한 상차 및 하차 작업의 횟수의 합의 최솟값을 출력한다.

제한

• 2ドル \le N \le 100,000円$
• 1ドル \le a_i \le 1,000円,000円$
• 1ドル \le i < j \le N$

힌트