题目描述

一棵树有n个节点，n-1条边。第i条边连接的两个结点是u[i]和v[i]。第i个结点有一个权值a[i]。对于任意的1<=i<j<=n，给出一些定义：

1、定义Path[i][j]表示结点i到结点j的简单路径上的所有结点的集合。

2、定义gcd[i][j]表示Path[i][j]集合内所有结点的权值的最大公约数。

3、定义size[i][j]表示结点i到结点j的简单路径所包含的结点数量（包含结点i和j)。

4、定义cost[i][j] = size[i][j] × gcd[i][j]。

你的任务是：对于任意的1<=i<j<=n，求cost[i][j]的总和，则求：


输入格式

第一行，一个整数n。

第二行，n个整数，第i个整数是a[i]。

接下有n-1行，第i行是两个整数u[i]和v[i]，1<= u[i]<v[i]<=n, 表示树的第i条边。

【数据范围】

对于50%的数据， 1<=n<=1000,    1<=a[i]<=100000。

对于100%的数据，1<=n<=100000,  1<=a[i]<=100000。

输出格式

一个整数。

输入/输出例子1

4
24 30 28 7
1 2
1 3
3 4

47

输入/输出例子2

10
180 168 120 144 192 200 198 160 156 150
1 2
2 3
2 4
2 5
5 6
4 7
7 8
7 9
9 10

1184