Common Divisor LCA

You are given a rooted tree with n nodes, where the root is node 1. Each node i has an integer value a_i. Your task is to count the number of ordered pairs of nodes \((x, y)\) (note that when x \neq y, the pairs \((x, y)\) and \((y, x)\) are considered different) such that the following condition holds:

[ a_{\mathrm{lca}(x,y)};\text{divides}; a_x \quad \text{and} \quad a_{\mathrm{lca}(x,y)} ;\text{divides}; a_y. ]

Here, \(\mathrm{lca}(x,y)\) represents the lowest common ancestor of nodes x and y in the tree. In other words, if we denote \(d = a_{\mathrm{lca}(x,y)}\), then the condition is that \(d\) is a common divisor of both \(a_x\) and \(a_y\) (i.e. \(a_x \mod d = 0\) and \(a_y \mod d = 0\)).

inputFormat

The first line contains an integer n representing the number of nodes in the tree.

The second line contains n integers: a₁, a₂, \dots, a_n, where a_i is the value associated with node i.

Each of the next n-1 lines contains two integers u and v indicating that there is an edge between nodes u and v.

outputFormat

Output a single integer—the number of ordered pairs \((x, y)\) that satisfy the condition described in the problem.

sample

3
2 4 6
1 2
1 3

9