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

You are given a tree with $N$ nodes. Each node has values assigned to it, <tex> value_i </tex>. You must calculate the sum cost of every pair nodes $(u, v)$, where <tex>gcd(value_u, value_v) > 1</tex> and $u$ &ne; $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.

Poveste şi cerinţă...

h2. Date de intrare

The first line of the input will contain $N$, the number of nodes. The second line will contain $N$ numbers, the $i-th$ number, representing the <tex>value_i</tex>. Each of the next $N - 1$ lines will contain a pair of nodes $(u, v)$, each representing an edge of the tree.

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

h2. Date de ieşire

The output will contain the sum of costs over all pairs of nodes $(u, v)$, such that <tex>gcd(value_u, value_v) > 1</tex>

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

h2. Restricţii

* 1 ≤ $N$ ≤ 100000
* 1 &le; <tex>value_i</tex> &le; 30000
* For the first subtask (1 &le; $N$ &le; 1000)
* For the second subtask, <tex> value_i = value_1 </tex> for $i = 1, 2,...n$
 

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

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

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

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

|

h3. Explicaţie
 
...
 

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