题目背景

此题是中山市第十二届义务教育段学生信息学邀请赛初中组 T6。

搬题人补充：出题人的原题面如下。（原题目名称：Where is a tree,there is a way）

题目背景：

从认识你，到与你性命相连，我从未后悔过。

——《大鱼海棠》

题目描述：

“菲，我们就这样永别了吗？”

“王总，我不过是你生命的一个过客。”

”但是，你救了我，我为你活着，离开你我也就再也不知道为什么而活了。

我将活成一个亡灵，因为时间会磨灭我的初心……”

……

他依稀记得，人的命运可以描述成一颗树，树的根为 $1$，每个人都在不断地从父亲走向儿子，每个生命阶段可以看为树上的一个点；两个性命相连却因命运相失的人，命运树是一样的，但会因为他们不同的选择，走向不同的方向，甚至磨灭初心。具体地，每个生命阶段有一个特征权值 $a$，因为生命的每个阶段都是独特的，所以 $a$ 两两不同。对于两个性命相连的人，不妨设其在 $x,y$ 这两个生命阶段，那么他们的初心是否磨灭，在于他们是否还记得他们分开的点，即若他们在 $z=\text{lca}(x,y)$ 分开，那么如果 $z$ 满足 $a_z$ 为 $a_x$，$a_y$ 的一个公约数，那么初心就还未磨灭。

他已经记不清分离的那一天了，也不知道自已将会走到哪里，但他希望，在记忆的最深处，他还记得她，记得回报的初心。

现在，他告诉了你他和她的命运树，他不知道他和她会走向哪里，只想知道在所有可能的情况中，有多少种，他们都还记得初心。

题目描述

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

输入格式

第一行一个整数 $n$。

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

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

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

11

说明/提示

【样例 $1$ 解释】

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

【样例 $2$】

见附件下发压缩包中的 $\textit{\textbf{ex\_tree2.in}}$ 与 $\textit{\textbf{ex\_tree2.ans}}$。

【样例 $3$】

见附件下发压缩包中的 $\textit{\textbf{ex\_tree3.in}}$ 与 $\textit{\textbf{ex\_tree3.ans}}$。

【样例 $4$】

见附件下发压缩包中的 $\textit{\textbf{ex\_tree4.in}}$ 与 $\textit{\textbf{ex\_tree4.ans}}$。

【测试点约束】

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

子任务编号	测试点数目	$n$	附加条件	子任务分数
$1$	$2$	$\le150$	无	$10$
$2$	$4$	$\le1500$
$3$	$2$	$\le10^5$	树为随机生成
$4$		$=99998$	$a_i\le300$
$5$		$=99999$	$a$ 为 $1\sim n$ 的排列
$6$	$8$	$\le10^5$	无	$50$

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

附件下载

tree