题目描述

Yoimiya 给了云浅 $n$ 堆火药，它们通过 $n-1$ 条引线互相连接，编号分别为 $1,2,\cdots,n$。保证任意两个火药均能通过某些引线直接或间接连接；也就是说，这 $n$ 堆火药与 $n-1$ 条引线构成了一棵树。

Yoimiya 认为，如果某些火药 $p_1,p_2,\cdots,p_k(k\ge 1)$ 满足对任意的 $1\le i<k$，均存在一条连接 $p_i,p_{i+1}$ 的引线，那么就认为这些火药可以用来放一次烟花。但并非所有的烟花都是安全的。具体来说，编号为 $i$ 的火药具有 $a_i$ 的危险度，对于一个放烟花的方案 $p_1,p_2,\cdots,p_k$，如果存在 $1\le i\neq j\le k$ 使得 $a_{p_i}$ 是 $a_{p_j}$ 的倍数，那么这个烟花方案就是危险的；反之，这个烟花方案就是安全的。

Yoimiya 想要让云浅算出，有多少种烟花方案是安全的。两种放烟花的方案 $p_1,\cdots,p_x$ 与 $q_1,\cdots,q_y$ 被认为是不同的，当且仅当以下两种条件中的至少一种被满足：

• $x\neq y$
• $\exist 1\le i\le x,p_i\neq q_i$。

Yoimiya 制作出来的火药十分特殊，因此，对任意的 $i\neq j$，均有 $a_i\neq a_j$，且 $1\le a_i\le n$。换言之，$a$ 是 $1,2,\cdots,n$ 的一个排列。

输入格式

第一行一个正整数 $n$，表示火药的个数。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示每个火药的危险度。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示存在一条连接 $u,v$ 的引线。

输出格式

输出一行一个正整数表示答案。

样例 $1$ 输入

6
1 5 3 2 4 6 
5 3
3 6
2 3
4 2
1 2

样例 $1$ 输出

16

样例 $1$ 解释

不难验证，一共有 $16$ 种方案是安全的。例如：

• 例如，一个安全的方案是使用 $\{2,3,5\}$ 这三堆火药，它们的危险值分别为 $3,4,5$，其中不存在某个数是另一个的倍数。
• 再如，一个不安全的方案是使用 $\{2,3,6\}$ 这三堆火药，它们的危险值分别为 $3,5,6$，其中 $6=3\times 2$，因此容易发生爆炸。

具体地，十六种方案分别是：

• $(1)$
• $(2)$
• $(2,3)$
• $(2,3,5)$
• $(2,4)$
• $(3)$
• $(3,5)$
• $(3,2)$
• $(3,2,4)$
• $(4)$
• $(4,2)$
• $(4,2,3)$
• $(5)$
• $(5,3)$
• $(5,3,2)$
• $(6)$

子任务约束

对于 $100\%$ 的数据，$1\le a_i\le n\le 10^5$，若 $i\neq j$，则 $a_i\neq a_j$。

• 特殊性质 A：存在一个点 $x$，使得对任意的 $y\neq x$，均存在连接 $x,y$ 的引线。
• 特殊性质 B：对于每个火药 $x$，与 $x$ 直接相连的火药数量均不超过 $2$。