Surprise me!
Contest: Codeforces Round 415 (Div. 1)
Difficulty rating: 3100
Tags: divide and conquer, math, number theory, trees

Tired of boring dates, Leha and Noora decided to play a game.

Leha found a tree with n vertices numbered from 1 to n. We remind you that tree is an undirected graph without cycles. Each vertex v of a tree has a number av written on it. Quite by accident it turned out that all values written on vertices are distinct and are natural numbers between 1 and n.

The game goes in the following way. Noora chooses some vertex u of a tree uniformly at random and passes a move to Leha. Leha, in his turn, chooses (also uniformly at random) some vertex v from remaining vertices of a tree (v ≠ u). As you could guess there are n(n - 1) variants of choosing vertices by players. After that players calculate the value of a function f(u, v) = φ(au·av) · d(u, v) of the chosen vertices where φ(x) is Euler's totient function and d(x, y) is the shortest distance between vertices x and y in a tree.

Soon the game became boring for Noora, so Leha decided to defuse the situation and calculate expected value of function f over all variants of choosing vertices u and v, hoping of at least somehow surprise the girl.

Leha asks for your help in calculating this expected value. Let this value be representable in the form of an irreducible fraction $$\frac{p}{q}$$. To further surprise Noora, he wants to name her the value $$P \cdot Q^{-1} \mod 10^9 + 7$$.

Help Leha!

Input format:
The first line of input contains one integer number n (2 ≤ n ≤ 2·105)  — number of vertices in a tree.

The second line contains n different numbers a1, a2, ..., an (1 ≤ ai ≤ n) separated by spaces, denoting the values written on a tree vertices.

Each of the next n - 1 lines contains two integer numbers x and y (1 ≤ x, y ≤ n), describing the next edge of a tree. It is guaranteed that this set of edges describes a tree.

Output format:
In a single line print a number equal to P·Q - 1 modulo 109 + 7.

Constraints:
Time limit: 8.0 s
Memory limit: 256.0 MB

Note:
Euler's totient function φ(n) is the number of such i that 1 ≤ i ≤ n,and gcd(i, n) = 1, where gcd(x, y) is the greatest common divisor of numbers x and y.

There are 6 variants of choosing vertices by Leha and Noora in the first testcase:

- u = 1, v = 2, f(1, 2) = φ(a1·a2)·d(1, 2) = φ(1·2)·1 = φ(2) = 1
- u = 2, v = 1, f(2, 1) = f(1, 2) = 1
- u = 1, v = 3, f(1, 3) = φ(a1·a3)·d(1, 3) = φ(1·3)·2 = 2φ(3) = 4
- u = 3, v = 1, f(3, 1) = f(1, 3) = 4
- u = 2, v = 3, f(2, 3) = φ(a2·a3)·d(2, 3) = φ(2·3)·1 = φ(6) = 2
- u = 3, v = 2, f(3, 2) = f(2, 3) = 2

Expected value equals to $${ \frac { 1 } { 6 } } \cdot ( 1 + 1 + 4 + 4 + 2 + 2 ) = { \frac { 1 4 } { 6 } } = { \frac { 7 } { 3 } }$$. The value Leha wants to name Noora is 7·3 - 1 = 7·333333336 = 333333338 $$\mod 10^9+7$$.

In the second testcase expected value equals to $$\frac{160}{20} = \frac{8}{1}$$, so Leha will have to surprise Hoora by number 8·1 - 1 = 8 $$\mod 10^9+7$$.

Example input:
3
1 2 3
1 2
2 3

Example output:
333333338

Example input:
5
5 4 3 1 2
3 5
1 2
4 3
2 5

Example output:
8

Editorial:
Here φ(x) denotes Euler's totient function of x, gcd(x, y) is the greatest common divisor of x and y and f(x) denotes the amount of divisors of x.
Small remark. We need to find the answer in the form of $$\frac{p}{q}$$, where gcd(P, Q) = 1. Let A will be the sum of all pairwise values f(u, v) and B is the amount of such pairs i.e. n(n - 1) and let g = gcd(A, B). Then P = A·g - 1, Q = B·g - 1 and the answer for the problem is P·Q - 1 = A·g - 1·B - 1·g = A·B - 1 which means there is no need to know g.
As it often happens in the problems where you are required to calc anything over all paths of a tree it's a good idea to use so-called centroid decomposition of a tree. Shortly, decomposition chooses some node of a tree, processes each path going through it and then deletes this node and solves the problem in the remaining forest recursively. It's obvious there is no matter what node we choose the answer will be always calculated correctly but total run-time depends on choosing this node. It's claimed each tree contains such a vertex with the removal of which all the remaining trees will have a size at least twice less then a size of this tree. So if we always choose such a vertex, each node of a tree will exist no more than in $$\log N$$ trees built by desomposition which is good enough.
Let's build centroid decomposition of the given tree. Let's root is the root of the current tree. Let's solve the problem for this tree (let's call it 'layer') and solve it for the sons of root recursively after that.
At first, $$\phi(ab) = \frac{\phi(a) \cdot \phi(b) \cdot g}{\phi(g)}$$ where g = gcd(a, b).
Also for the current layer dist(u, v) = du + dv where dx is the distance from root to x.
Let's fix some vertex v. How to calc the sum φ(av·av)·dist(u, v) inside our layer over all such u that the path $$u \rightarrow v$$ goes through root? Let's denote the set of such u as A(v). We want to add to the answer $$$$
$$= \sum_{u \in A(v)} \left( \phi(a_v) \cdot \phi(a_u) \cdot \frac{g}{\phi(g)} \cdot d_v + \phi(a_v) \cdot \phi(a_u) \cdot \frac{g}{\phi(g)} \cdot d_u \right)$$, where g = gcd(au, av).
Considering we need to sum up all such sums over each v from the layer, the sum current layer increases the total sum equals to $$$$.
So we need to be able to sum up $$\sum_{u \in A(v)} \frac{\phi(a_u) \cdot g}{\phi(g)}$$, g = gcd(au, av) for each v. Let's understand how to calc sumg for each g which means the sum of Euler's totient functions of all such vertices u, that has gcd⁡(av, au) = g. Let's imagine we know sumphic which denotes the sum of φ(au) for such u that $$a_{u} \mod c = 0$$. Then the following statement is true:
$$$$.
We can calculate values of sumphi in $${ \mathcal { O } } ( n \ln n \log n )$$ time: each divisor of each number in range from 1 to n (which is, as it known, $${\mathcal {O}}(n\ln n)$$) will be counted in $${\mathcal {O}}(\log n)$$ layers of the centroid decomposition.
So we're already able to calc sum values in the time apparently proprtional to $${\mathcal {O}}(n\log ^{2}n)$$. More precisely, the number of operations we waste for calculating sum will be equal to $$\sum f(x)$$ over all such i and x that (1 ≤ x, i ≤ n, $$i \mod x = 0$$, where f(x) is the amount of divisors of x. This sum is equivalent to $$\sum_{i=1}^{n}\frac{n}{i}\cdot f(i)$$. Coding this solution carefully can give you Accepted thanks to high TL we set to Java solution. I can prove only $${\mathcal {O}}(n\log ^{3}n)$$ complexity for this solution which is a very high upper bound. Can anyone give any better complexity for $$\sum_{i=1}^{n}\frac{n}{i}\cdot f(i)$$?
However we can speed up this solution. Here we calculated $$\sum_{g, a_v \mod g = 0} sum_g \cdot \frac{g}{\phi(g)}$$ giving that sumg was equal to $$\sum_{x \neq g, x \mod g = 0} \sum_x$$ leading to $$o \left( \sum_{g, a_v \mod g = 0} f(g) \right)$$ complexity for each v in the layer.
Actually the sum $$\sum_{g,x \mod g=0} \frac{g}{\phi(g)} \cdot sum_g$$ for each x can be showed as $$\sum_{g,x \mod g=0} c_x[g] \cdot sumphi_g$$ using some coefficients cx[]. If we find them we'll be able to process each v of the layer in O(f(av)) time which leads to final $${ \mathcal { O } } ( n \ln n \log n )$$ complexity.
Let's precalculate these coefficients in ascending order for each x. It's easy to see that c1[1] = 1 and for a prime p $$c_{p}[1] = 1, \; c_{p}[p] = \frac{1}{p-1}$$. Now let's x is a composite number and let's p is it's least prime divisor and α is such maximum number that x is divisible by pα, and $$q = \frac{x}{p^\alpha}$$. Then coefficients for any divisor z of x can be calculated in the following way:
• If $$z \mod p \neq 0$$ then cx[z] = cq[z],
• $$c_x[z] = c_q[z] + \frac{c_q[z/p]}{p-1}$$ otherwise.
Total complexity: $${ \mathcal { O } } ( n \ln n \log n )$$.