4004: 【NOIP2022赛前集训】和谐友爱(friend)
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：20
解决：8
题目描述
friend.in/out/cpp
给定 $n$ 个节点的树，初始每个节点有权值 $v_i$。
两个有直接连边的人是朋友，但是对于边 $(x,y)$，如果 $\gcd(v_x,v_y)=1$，那么他们的友谊是不牢固的。
为了让大家友谊牢固，你可以修改某些点的权值，每次修改你可以任选一个节点并把它的权值改为任意值 $x$，同时耗费 $x$ 的代价。
你可以进行任意次修改，求使得任意有直接连边的两点 $(x,y)$ 都有 $\gcd(v_x,v_y)>1$ 的最小代价。
给定 $n$ 个节点的树，初始每个节点有权值 $v_i$。
两个有直接连边的人是朋友，但是对于边 $(x,y)$，如果 $\gcd(v_x,v_y)=1$，那么他们的友谊是不牢固的。
为了让大家友谊牢固，你可以修改某些点的权值，每次修改你可以任选一个节点并把它的权值改为任意值 $x$，同时耗费 $x$ 的代价。
你可以进行任意次修改，求使得任意有直接连边的两点 $(x,y)$ 都有 $\gcd(v_x,v_y)>1$ 的最小代价。
输入
第一行一个正整数 $n$，表示树的节点个数。
接下来的一行 $n$ 个正整数，第 $i$ 个数表示 $v_i$。
接下来 $n-1$ 行，每行两个正整数 $u,v$，表示一条树边。保证整棵树连通。
接下来的一行 $n$ 个正整数，第 $i$ 个数表示 $v_i$。
接下来 $n-1$ 行，每行两个正整数 $u,v$，表示一条树边。保证整棵树连通。
输出
一行一个正整数，表示最小代价。
样例输入 复制
6
5 6 3 4 9 12
1 2
1 3
1 4
1 6
3 5样例输出 复制
6提示
数据范围及提示
对于所有数据，有 $n,\max v_i \leq 1000$。
- subtask1（$10\text{pts}$）：满足 $n,\max v_i\leq 10$。
- subtask2（$30\text{pts}$）：满足 $n,\max v_i\leq 100$。且整棵树是一条 $1\to 2\to\cdots\to n$ 的链。
- subtask3（$60\text{pts}$）：无特殊性质。
对于所有数据，有 $n,\max v_i \leq 1000$。
- subtask1（$10\text{pts}$）：满足 $n,\max v_i\leq 10$。
- subtask2（$30\text{pts}$）：满足 $n,\max v_i\leq 100$。且整棵树是一条 $1\to 2\to\cdots\to n$ 的链。
- subtask3（$60\text{pts}$）：无特殊性质。