English · Original
Chinese · Translation
Formal · Original
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 _a__v_ 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_) = φ(_a__u_·_a__v_) · _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 . To further surprise Noora, he wants to name her the value .
Help Leha!
## Input
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 _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _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
In a single line print a number equal to _P_·_Q_ - 1 modulo 109 + 7.
[samples]
## 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) = φ(_a_1·_a_2)·_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) = φ(_a_1·_a_3)·_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) = φ(_a_2·_a_3)·_d_(2, 3) = φ(2·3)·1 = φ(6) = 2
* _u_ = 3, _v_ = 2, _f_(3, 2) = _f_(2, 3) = 2
Expected value equals to . The value Leha wants to name Noora is 7·3 - 1 = 7·333333336 = 333333338 .
In the second testcase expected value equals to , so Leha will have to surprise Hoora by number 8·1 - 1 = 8 .
厌倦了无聊的约会，Leha 和 Noora 决定玩一个游戏。
Leha 找到一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]。我们提醒你，树是一种无环无向图。树中每个顶点 #cf_span[v] 上写有一个数字 #cf_span[av]。巧合的是，所有写在顶点上的数值互不相同，且是介于 #cf_span[1] 和 #cf_span[n] 之间的自然数。
游戏规则如下：Noora 从树中均匀随机选择一个顶点 #cf_span[u]，并将回合交给 Leha。Leha 在他的回合中，从剩余的顶点中（#cf_span[v ≠ u]）均匀随机选择一个顶点 #cf_span[v]。可以想象，玩家选择顶点的方案共有 #cf_span[n(n - 1)] 种。之后，双方计算所选顶点的函数值 #cf_span[f(u, v) = φ(au·av)] #cf_span[·] #cf_span[d(u, v)]，其中 #cf_span[φ(x)] 是欧拉函数，#cf_span[d(x, y)] 是树中顶点 #cf_span[x] 和 #cf_span[y] 之间的最短距离。
很快，Noora 觉得这个游戏无聊了，于是 Leha 决定缓解气氛，计算函数 #cf_span[f] 在所有选择顶点 #cf_span[u] 和 #cf_span[v] 的方案中的期望值，希望能以某种方式让女孩感到惊喜。
Leha 请求你帮助他计算这个期望值。设该值可表示为最简分数形式 。为更进一步地让 Noora 惊讶，他想告诉她这个值 。
帮助 Leha！
输入的第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 2·105)] —— 树中顶点的数量。
第二行包含 #cf_span[n] 个不同的数 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ n)]，用空格分隔，表示写在树顶点上的数值。
接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]，描述树的一条边。保证这些边构成一棵树。
请在一行中输出一个等于 #cf_span[P·Q - 1] 对 #cf_span[109 + 7] 取模的数。
欧拉函数 #cf_span[φ(n)] 是满足 #cf_span[1 ≤ i ≤ n] 且 #cf_span[gcd(i, n) = 1] 的整数 #cf_span[i] 的个数，其中 #cf_span[gcd(x, y)] 表示 #cf_span[x] 和 #cf_span[y] 的最大公约数。
在第一个测试用例中，Leha 和 Noora 有 #cf_span[6] 种选择顶点的方案：
期望值等于 。Leha 想要告诉 Noora 的值是 #cf_span[7·3 - 1 = 7·333333336 = 333333338] 。
在第二个测试用例中，期望值等于 ，因此 Leha 需要告诉 Hoora 的数字是 #cf_span[8·1 - 1 = 8] 。
## Input
输入的第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 2·105)] —— 树中顶点的数量。
第二行包含 #cf_span[n] 个不同的数 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ n)]，用空格分隔，表示写在树顶点上的数值。
接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]，描述树的一条边。保证这些边构成一棵树。
## Output
请在一行中输出一个等于 #cf_span[P·Q - 1] 对 #cf_span[109 + 7] 取模的数。
[samples]
## Note
欧拉函数 #cf_span[φ(n)] 是满足 #cf_span[1 ≤ i ≤ n] 且 #cf_span[gcd(i, n) = 1] 的整数 #cf_span[i] 的个数，其中 #cf_span[gcd(x, y)] 表示 #cf_span[x] 和 #cf_span[y] 的最大公约数。
在第一个测试用例中，Leha 和 Noora 有 #cf_span[6] 种选择顶点的方案：
#cf_span[u = 1], #cf_span[v = 2], #cf_span[f(1, 2) = φ(a1·a2)·d(1, 2) = φ(1·2)·1 = φ(2) = 1]
#cf_span[u = 2], #cf_span[v = 1], #cf_span[f(2, 1) = f(1, 2) = 1]
#cf_span[u = 1], #cf_span[v = 3], #cf_span[f(1, 3) = φ(a1·a3)·d(1, 3) = φ(1·3)·2 = 2φ(3) = 4]
#cf_span[u = 3], #cf_span[v = 1], #cf_span[f(3, 1) = f(1, 3) = 4]
#cf_span[u = 2], #cf_span[v = 3], #cf_span[f(2, 3) = φ(a2·a3)·d(2, 3) = φ(2·3)·1 = φ(6) = 2]
#cf_span[u = 3], #cf_span[v = 2], #cf_span[f(3, 2) = f(2, 3) = 2]
期望值等于 。Leha 想要告诉 Noora 的值是 #cf_span[7·3 - 1 = 7·333333336 = 333333338] 。
在第二个测试用例中，期望值等于 ，因此 Leha 需要告诉 Hoora 的数字是 #cf_span[8·1 - 1 = 8] 。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 2 \cdot 10^5 $, be the number of vertices in a tree.
Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $, where $ a_i $ is the value on vertex $ i $.
Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, 2, \dots, n\} $ and edge set $ E $ of size $ n-1 $.
Let $ d(u, v) $ denote the shortest path distance (number of edges) between vertices $ u $ and $ v $ in $ T $.
Let $ \varphi(x) $ denote Euler’s totient function.
**Constraints**
1. All $ a_i \in \{1, 2, \dots, n\} $ are distinct.
2. The graph $ T $ is a tree (connected, acyclic, undirected).
**Objective**
Compute the expected value of $ f(u, v) = \varphi(a_u \cdot a_v) \cdot d(u, v) $ over all ordered pairs $ (u, v) $ with $ u \ne v $:
$$
\mathbb{E}[f] = \frac{1}{n(n-1)} \sum_{\substack{u,v=1 \\ u \ne v}}^{n} \varphi(a_u \cdot a_v) \cdot d(u, v)
$$
Let $ \frac{P}{Q} $ be the irreducible form of $ \mathbb{E}[f] $.
Output $ P \cdot Q^{-1} \mod (10^9 + 7) $, where $ Q^{-1} $ is the modular multiplicative inverse of $ Q $ modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. Surprise me!",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 8000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF809E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Tired of boring dates, Leha and Noora decided to play a game.\n\nLeha 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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "厌倦了无聊的约会，Leha 和 Noora 决定玩一个游戏。\n\nLeha 找到一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]。我们提醒你，树是一种无环无向图。树中每个顶点 #cf_span[v] 上写有一个数字 #cf_span[av]。巧合的是，所有写在顶点上的数值互不相同，且是介于 #cf_span[1] 和 #cf_span[n]...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 2 \\cdot 10^5 $, be the number of vertices in a tree. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $, where ...",
"is_translate": false,
"language": "Formal"
}
]
}