27653번 - 최소 트리 분할

문제

정점이 $N$개인 트리가 주어진다. 정점에는 1ドル$부터 $N$까지 번호가 붙어있다. 각 정점에는 가중치가 존재하는데, 초기에 모든 가중치는 0ドル$이다.

당신은 다음 연산을 트리에 반복하여 1ドル$ 이상 $N$ 이하의 모든 $i$에 대해 정점 $i$의 가중치가 $A_i$가 되도록 만들고 싶다.

• 연산: 주어진 트리의 임의의 부분 연결 그래프에 대하여, 그 그래프에 포함되는 정점의 가중치를 1ドル$씩 증가시킨다.

1ドル$ 이상 $N$ 이하의 모든 $i$에 대해 정점 $i$의 가중치가 $A_i$가 되도록 하는 최소 연산 횟수를 구하라.

입력

첫 번째 줄에 정점의 개수를 나타내는 $N$이 주어진다. (2ドル \leq N \leq 100,000円$)

두 번째 줄에 목표 가중치 $A_1, A_2, \dots, A_N$이 공백에 구분되어 주어진다. (0ドル \leq A_i \leq 10^9$)

세 번째 줄부터 $(N - 1)$개의 줄에 걸쳐 간선의 정보 $u_i$ $v_i$가 주어지며, 이는 $u_i$번 정점과 $v_i$번 정점 사이에 간선이 있다는 뜻이다. (1ドル \leq u_i, v_i \leq N$)

출력

최소 연산 횟수를 출력하라.

제한

힌트