Statement

Filippo has found a weird tree (a connected acyclic graph), with N nodes indexed from 1 to N and N-1 edges, each node has a value V_i. He is studying the tree thoroughly, but is struggling to compute its Beauty, which is defined in the following way: (1) The correlation of a pair of nodes (i,j) is the sum of the values on the path that connects them, including i and j. (2) The beauty of the tree is the sum of the Correlation over all pairs (i,j), such that i≠ j and gcd(V_i, V_j) ≠ 1. (3) The gcd (i.e. the greatest common divisor) of 2 natural numbers a and b is the largest natural number that divides both a and b. Help Filippo find the Beauty of the weird tree.