← 返回题目列表

Codeforces · 809/E

E. 给我一个惊喜!

中文机器翻译题面 查看原题

厌倦了无聊的约会,Leha 和 Noora 决定玩一个游戏。

Leha 找到了一棵有 n 个顶点的树,编号从 1 到 n。我们提醒您,树是没有环的无向图。树的每个顶点 v 上都写有一个数字 av 。非常偶然的是,写在顶点上的所有值都是不同的,并且是 1 到 n 之间的自然数。

游戏按以下方式进行。 Noora 均匀随机选择树的某个顶点 u 并将移动传递给 Leha。 Leha 又从树的剩余顶点中选择(也是均匀随机地)某个顶点 v (v ≠ u)。正如您所猜测的,玩家选择顶点有 n(n - 1) 种变体。之后,玩家计算所选顶点的函数 f(u, v) = φ(au·av) · d(u, v) 的值,其中 φ(x) 是欧拉函数,d(x, y) 是树中顶点 x 和 y 之间的最短距离。

很快,游戏对 Noora 来说就变得无聊了,所以 Leha 决定化解这种情况,并计算函数 f 在选择顶点 u 和 v 的所有变体上的期望值,希望至少能以某种方式给女孩带来惊喜。

Leha 请求您帮助计算此期望值。令该值可以用不可约分数 $$\frac{p}{q}$$ 的形式表示。为了进一步让 Noora 感到惊讶,他想将她的值命名为 $$P \cdot Q^{-1} \mod 10^9 + 7$$。

帮助莱哈!

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 2·105) — 树中的顶点数。

第二行包含 n 个不同的数字 a1, a2, ..., an (1 ≤ ai ≤ n),用空格分隔,表示写在树顶点上的值。

接下来的 n - 1 行中的每一行都包含两个整数 x 和 y (1 ≤ x, y ≤ n),描述树的下一条边。保证这组边描述一棵树。

输出

在一行中打印一个等于 P·Q - 1 模 109 + 7 的数字。

示例

输入 #1

3
1 2 3
1 2
2 3

输出 #1

333333338

输入 #2

5
5 4 3 1 2
3 5
1 2
4 3
2 5

输出 #2

8

注意

欧拉 totient 函数 φ(n) 是满足 1 ≤ i ≤ n 且 gcd(i, n) = 1 的 i 的个数,其中 gcd(x, y) 是数字 x 和 y 的最大公约数。

在第一个测试用例中,Leha 和 Noora 有 6 种选择顶点的变体:

- 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

期望值等于 $${ \frac { 1 } { 6 } } \cdot ( 1 + 1 + 4 + 4 + 2 + 2 ) = { \frac { 1 4 } { 6 } } = { \frac { 7 } { 3 } }$$。 Leha 想要命名 Noora 的值为 7·3 - 1 = 7·333333336 = 333333338 $$\mod 10^9+7$$。

在第二个测试用例中,预期值等于 $$\frac{160}{20} = \frac{8}{1}$$,因此 Leha 必须用数字 8·1 - 1 = 8 $$\mod 10^9+7$$ 给 Hoora 带来惊喜。