题目描述

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

输入

从文件tree.in中读入数据。

第一行一个整数$n$。

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

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

输出

输出到文件tree.out中。

一行一个整数表示答案。

样例数据$1$

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

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$

见下载中的ex_tree2.in与ex_tree2.ans。

样例$3$

见下载中的ex_tree3.in与ex_tree3.ans。

样例$4$

见下载中的ex_tree4.in与ex_tree4.ans。

数据范围

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

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