题目描述

你有一棵以 1 为根的树，统计点对 $(x, y)$，满足 $a_{lca(x,y)}$ 是 $a_x$ 和 $a_y$ 的公约数。注意当 $x \neq y$ 时 $(x, y)$ 和 $(y, x)$ 视为不同的点对。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

第三到 $n + 1$ 行，每行两个整数，表示树上的边。

输出格式

一行一个整数表示答案。

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

11

提示

样例解释

以下点对满足条件：$(1, 1)$，$(1, 3)$，$(1, 5)$，$(2, 2)$，$(3, 1)$，$(3, 3)$，$(3, 5)$，$(4, 4)$，$(5, 1)$，$(5, 3)$，$(5, 5)$。

数据范围

本题数据分为多个子任务，具体如下：

对于所有数据，保证 $1 \leq a_i \leq n$。