반짝임이 있는 곳

시간 제한2초메모리 제한1024 MB

요약

트리와 목표 수열이 주어질 때, 서로 겹치지 않거나 포함 관계인 서브트리 덧셈 연산의 최소 횟수를 구한다.

문제

나나는 정점이 $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$ 로 만들기 위해 필요한 연산의 최소 횟수를 출력한다.