== 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 <tex>(u, v)</tex>, where <tex>gcd(value_u, value_v) > 1</tex> and $u$ ≠ $v$. For a pair of nodes <tex>(u, v)<tex>, we define the cost of that path to be the sum of value of all nodes that lie inside the <tex>(u, v)</tex> path.
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$ ≠ $v$. For a pair of nodes <tex>(u, v)<tex>, we define the cost of that path to be the sum of value of all nodes that lie inside the <tex>(u, v)</tex> path.
h2. Date de intrare
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.
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 <tex>value_i</tex> (1 ≤ <tex>value_i</tex> ≤ 30000). Each of the next $N - 1$ lines will contain a pair of nodes $(u, v)$, each representing an edge of the tree.
For tests worth $20$ points (1 ≤ $N$ ≤ 1000)
For tests worth $20$ more points, <tex> value[i] = value[1] </tex> for $i = 1, 2,...n$
