GCD Harmony

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

요약

트리의 각 노드에 새 양의 정숫값을 부여해 모든 인접한 두 노드의 최대공약수가 1보다 크도록 하면서, 새 값들의 합을 최소로 만든다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트리, 정수론, DFS
정답자: 아직 제출이 없습니다

문제

Consider a tree with undirected edges, where each node has an integer value. Adjacent nodes are said to be GCD-harmonic if the greatest common divisor (GCD) of their values is strictly greater than $1$ .

You can modify the value of any tree node to any positive integer. The cost of this operation is equal to the new node value, regardless of the node's original value. You can change as many node values as needed, and node values do not need to be unique.

What is the minimum total cost to make every pair of adjacent nodes in the tree GCD-harmonic?

입력

The first line of input contains a single integer $n$ ( $2 \leq n \leq 5\\,000$ ), which is the number of nodes in the tree. Tree nodes are numbered from $1$ to $n$ .

Each of the next $n$ lines contains an integer $v$ ( $1 \le v \le 100$ ). These are the initial values of the nodes (which are not guaranteed to be unique), in node number order.

Each of the next $n - 1$ lines contains two integers $a$ and $b$ ( $1 \leq a, b \leq n, a \neq b$ ), indicating a tree edge between nodes $a$ and $b$ . It is guaranteed that these edges form a tree.

출력

Output a single integer, which is the minimum total cost to make every pair of adjacent nodes in the tree GCD-harmonic.

예제2

예제 1
입력
```
6
5
6
3
4
9
12
1 2
1 3
1 4
1 6
3 5
```
예상 출력
```
6
```
예제 2
입력
```
3
1
2
3
3 1
2 3
```
예상 출력
```
4
```