思路：深度优先搜索

对于每个点，通过 DFS 找到这个点所在的同权值连通块。

在这个连通块内的所有点，两两之间的路径的权值的最小公倍数必然是 $3$ 或 $5$ 。

对于剩余的跨同权值连通块的点，其路径的权值的最小公倍数必然是 $15$ 。

可以先计算同权值连通块内的路径数，然后拿所有点之间的路径数减去同权值连通块内的路径数，即跨连通块的路径数。

题目描述

小红有一棵树，树上每个结点都有一个权值，权值是 $3$ 或者 $5$ ，

现在，小红想问你，对于每条路径，路径上的点的权值的最小公倍数之和是多少

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示树中结点数量。

第二行， $n$ 个整数，第 $i$ 个整数表示第 $i$ 个结点的权值 $a_i(a_i=3$ 或者 $a_i=5)$

接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i(1 \leq u_i,v_i \leq n)$ 表示结点 $u_i$ 和 $v_i$ 之间有一条边。

输出描述

一个整数，表示所有路径上的点的权值的最小公倍数之和

样例

输入

3
5 3 3
2 1
3 2

输出

33

说明

路径 $1-2$ 的权值最小公倍数为：$lcm(5,3)=15$

路径 $2-3$ 的权值最小公倍数为：$lcm(3,3)=3$

路径 $1-2-3$ 的权值最小公倍数为:$lcm(5,3,3)=15$

15+15+3=33