34066번 - 반짝임이 있는 곳

문제

나나는 정점이 $N$개인 트리 $T$를 가지고 있으며, 트리의 각 정점에는 수가 하나씩 적혀있다. 초기에 각 정점에 적혀있는 수는 전부 0ドル$이다.

나나는 다음과 같은 연산을 0ドル$번 이상 할 수 있다.

• 10ドル^9$ 이하의 양의 정수 $x$와 트리 $T$의 서브트리 $T'$를 원하는 대로 선택한 뒤, $T'$에 포함된 모든 정점에 적힌 수에 $x$를 더한다.
• 이때 $i$번째 연산에서 사용되는 서브트리의 정점의 집합을 $T'_i$라 할 때, $i \neq j$인 두 $i, j$에 대해 $T'_i$와 $T'_j$의 교집합이 공집합이거나 $T'_i$ 또는 $T'_j$ 둘 중 하나와 같아야 한다.

나나는 목표 수열 $B$가 주어졌을 때, $i$번째 정점에 적힌 수가 정확히 $B_i$가 되도록 만들고 싶다. 이때 필요한 연산의 최소 횟수를 구하자.

트리와 서브트리가 무엇인지 잘 모르는 친구들은 친절한 준호가 준비한 아래의 정의를 읽어보도록 하자.

• 정점들의 집합 $V$와 간선들의 집합 $E$으로 구성된 그래프 $G=(V,E)$가 트리라 함은 $G$의 임의의 두 정점 $u$와 $v$사이에 항상 경로가 존재하고 그 경로가 유일함을 의미한다.
• 트리 $T=(V,E)$의 서브트리 $T'=(V',E')$란, $V'\subseteq V,E'\subseteq E$이고 위의 트리의 성질을 만족하는 그 자체로 트리인 그래프이다.

입력

첫째 줄에 정점의 개수 $N$이 주어진다.

둘째 줄에 목표 수열을 의미하는 $N$개의 정수 $B_1,B_2,\cdots ,B_N$이 공백으로 구분되어 주어진다.

셋째 줄부터 $N-1$개의 줄에 걸쳐, 트리의 간선을 의미하는 두 정수 $u,v$가 한 줄에 하나씩 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점을 연결하는 간선을 의미한다.

출력

$i$번째 정점에 적힌 수를 $B_i$로 만들기 위해 필요한 연산의 최소 횟수를 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\leq N\leq 200,円 000$
• 1ドル\leq B_i\leq 10^9$ (1ドル\le i\le N$)
• 1ドル\le u,v\le N$
• 입력으로 주어지는 그래프는 트리이다.

힌트