== include(page="template/taskheader" task_id="sumtree") ==

You are given a tree with $N$ nodes. Each node has values assigned to it,  value[i]. You must calculate the sum cost of every pair nodes $(u, v)$, where $gcd(value[u], value[v]) > 1$ and $u$ ≠ $v$

You are given a tree with $N$ nodes. Each node has values assigned to it, value[i]. You must calculate the sum cost of every pair nodes $(u, v)$, where $gcd(value[u], value[v]) > 1$ and $u$ ≠ $v$. For a pair of nodes $(u, v)$, we define the cost of that path to be the sum of value of all nodes that lie inside the $(u, v)$ path.

h2. Date de intrare

Fişierul de intrare $sumtree.in$ ...

The first line of the input will contain $N$ (1 ≤ $N$ ≤ 100000), the number of nodes. The second line will contain $N$ numbers, the $i-th$ number, representing the value[i] (1 ≤ $value[i]$ ≤ 30000). Each of the next $N - 1$ lines will contain a pair of nodes $(u, v)$, each representing an edge of the tree.

h2. Date de ieşire

For tests worth $20$ points (1 ≤ $N$ ≤ 1000)
For tests worth $20$ more points, value[i] = value[1] for $i = 1, 2,...n$

În fişierul de ieşire $sumtree.out$ ...

h2. Date de ieşire

h2. Restricţii

The output will contain the sum of costs over all pairs of nodes $(u, v)$, such that $gcd(value[u], value[v]) > 1$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. sumtree.in |_. sumtree.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
2 7 14 22 77
1 2
1 3
2 4
4 5
 
| 442

|
h3. Explicaţie