CF809E Surprise me!

厌倦了无聊约会的 Leha 和 Noora 决定玩一个游戏。 Leha 找到了一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。我们提醒你，树是一种无环的无向图。树的每个顶点 $v$ 上写有一个数字 $a_{v}$。碰巧的是，所有顶点上的数字两两不同，且均为 $1$ 到 $n$ 的自然数。 游戏的规则如下：Noora 均匀随机地选择树上的一个顶点 $u$，然后轮到 Leha 行动。Leha 也均匀随机地从剩下的顶点中选择一个顶点 $v$（$v \neq u$）。显然，两人选择顶点的方式共有 $n(n-1)$ 种。 接下来，玩家们计算函数 $f(u,v)=\varphi(a_{u} \cdot a_{v}) \cdot d(u,v)$ 的值，其中 $\varphi(x)$ 表示欧拉函数，$d(x,y)$ 表示树上顶点 $x$ 和 $y$ 之间的最短距离。 很快这个游戏就令 Noora 感到无趣，于是 Leha 决定活跃气氛，计算所有选择顶点 $u$ 和 $v$ 的方案下函数 $f$ 的期望值，希望能让女孩惊喜一下。 Leha 请求你帮忙计算这个期望值。假设该期望值可以表示为最简分数 $\frac{P}{Q}$。为了更进一步给 Noora 惊喜，他希望你报出 $P \cdot Q^{-1} \bmod 10^9+7$ 的值。 请帮 Leha 完成这个任务！

输入的第一行包含一个整数 $n$，表示树的顶点数（$2 \leq n \leq 2 \cdot 10^{5}$）。 第二行包含 $n$ 个不同的数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq n$），分别表示每个顶点上的数。 接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x,y \leq n$），表示树上的一条无向边。保证这些边描述的是一棵树。

输出一行，给出一个数字，等于 $P \cdot Q^{-1} \bmod 10^9+7$。

欧拉函数 $\varphi(n)$ 表示 $1 \leq i \leq n$ 且 $\gcd(i,n)=1$ 的 $i$ 的个数，这里 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。 在第一个样例中，两人选择顶点的方案共有 $6$ 种： - $u=1$，$v=2$，$f(1,2)=\varphi(a_{1} \cdot a_{2}) \cdot d(1,2)=\varphi(1 \cdot 2)\cdot 1=\varphi(2)=1$ - $u=2$，$v=1$，$f(2,1)=f(1,2)=1$ - $u=1$，$v=3$，$f(1,3)=\varphi(a_{1} \cdot a_{3}) \cdot d(1,3)=\varphi(1 \cdot 3)\cdot 2=2\varphi(3)=4$ - $u=3$，$v=1$，$f(3,1)=f(1,3)=4$ - $u=2$，$v=3$，$f(2,3)=\varphi(a_{2} \cdot a_{3}) \cdot d(2,3)=\varphi(2 \cdot 3)\cdot 1=\varphi(6)=2$ - $u=3$，$v=2$，$f(3,2)=f(2,3)=2$ 期望值等于 $\frac{14}{6}=\frac{7}{3}$。Leha 想报告给 Noora 的值是 $7 \cdot 3^{-1}=7 \cdot 333333336 = 333333338$。 在第二个样例中，期望值为 $8$，Leha 想报告给 Hoora 的值为 $8 \cdot 1^{-1}=8$。 由 ChatGPT 5 翻译