34715번 - 트리 초기화

문제

트리를 가지고 놀던 재찬이는 문득 특정 연산을 몇 번 수행해야 트리를 초기화할 수 있을지 궁금해졌다.

트리 초기화란 가중치가 있는 $N$개의 정점을 가진 트리에서, 모든 정점의 가중치를 0ドル$으로 만드는 것을 의미한다.

트리에서는 다음 두 가지 연산을 수행할 수 있다.

1. 임의의 정점 $r$을 트리의 루트로 설정한다.
2. 부모 정점 $u$에서 자식 정점 $v$로 임의의 양의 정수 $x$만큼 가중치를 이동한다.

한 정점 $u$가 다른 정점 $v$의 부모라는 것은, $u$와 $v$가 간선으로 직접 연결되어 있으면서, 현재 설정된 루트에서 $v$로 가는 최단 경로가 $u$를 거쳐 감을 의미한다. $u$에서 $v$로 가중치를 $x$만큼 이동하면 $u$의 가중치는 $x$만큼 감소하고, $v$의 가중치는 $x$만큼 증가한다. 이 연산은 $u,ドル $v$의 현재 가중치와 무관하게 수행할 수 있다.

초기에는 루트가 설정되어 있지 않으며, 2ドル$번 연산을 수행하기 위해서는 1ドル$번 연산을 최소 한 번 수행해야 한다. 2ドル$번 연산은 얼마든지 사용할 수 있지만, 1ドル$번 연산의 횟수는 최소가 되도록 해야 한다.

트리를 초기화하는 데 필요한 1ドル$번 연산의 최소 횟수를 구해보자.

입력

첫째 줄에 정점의 개수 $N$이 주어진다. $(2 \leq N \leq 100,000円)$

둘째 줄에 $N$개 정점의 가중치 $W_i$가 공백을 사이에 두고 주어진다. $(|W_i| \leq 10^9,$ $W_i$는 정수$)$

이후 $N-1$개의 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 $u,ドル $v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점을 잇는 간선이 존재한다는 의미이다. (1ドル \leq u, v \leq N,ドル $u \ne v$)

출력

첫째 줄에 트리를 초기화하기 위해 필요한 1ドル$번 연산의 최소 횟수를 출력한다. 불가능하다면 -1을 출력한다.

제한

노트