题目描述

考虑一棵无向边组成的树，每个节点都有一个整数值。如果相邻两个节点的值的最大公约数严格大于 $1$，则称这两个节点是 GCD 和谐的。

你可以将任意树节点的值修改为任意正整数。此操作的代价等于修改后该节点的值，无论节点原来的值是多少。你可以根据需要修改任意多个节点的值，且修改后节点的值不必互不相同。

要使树中每一对相邻节点都变成 GCD 和谐的，所需的最小总代价是多少？

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 5{,}000$），表示树中节点的数量。节点的编号为 $1$ 到 $n$。

接下来的 $n$ 行，每行包含一个整数 $v$（$1 \le v \le 100$）。这些是按节点编号顺序给出的节点初始值（不保证互不相同）。

接下来的 $n - 1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n, a \ne b$），表示节点 $a$ 与 $b$ 之间的一条树边。保证这些边构成一棵树。

输出格式

输出一个整数，表示使树中每一对相邻节点都变成 GCD 和谐的最小总代价。

6
5
6
3
4
9
12
1 2
1 3
1 4
1 6
3 5

6

3
1
2
3
3 1
2 3

4

提示

翻译由 DeepSeek V3.2 完成