分析
$\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了...
首先要知道
$$
\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}
$$
可以暴力拆式子证明。
为了方便，设 $p_{a_i}=i$ 。
于是就可以来推一推式子了（推的比较长，如果想看简单的可以去看 xgzc 的）：
$$
\begin{aligned}
\text{原式}&=\sum_{i=1}^n\sum_{j=1}^n\varphi(ij)dis(p_i,p_j)\\
&=\sum_{i=1}^n\sum_{j=1}^n\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}dis(p_i,p_j)\\
&=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]\varphi(i)\varphi(j)dis(p_i,p_j)\\
&=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}[\gcd(i,j)=1]\varphi(id)\varphi(jd)dis(p_{id},p_{jd})\\
&=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/dk}\sum_{j=1}^{n/dk}\varphi(idk)\varphi(jdk)dis(p_{idk},p_{jdk})\\
&=\sum_{T=1}^n\sum_{d|T}\frac{d}{\varphi(d)}\mu\left(\frac{T}{d}\right)\sum_{i=1}^{n/T}\sum_{j=1}^{n/T}\varphi(iT)\varphi(jT)dis(p_{iT},p_{jT})\\
&=\sum_{T=1}^n\color{red}{\sum_{d|T}\frac{d}{\varphi(d)}\mu\left(\frac{T}{d}\right)}\sum_{T|i}\sum_{T|j}\varphi(i)\varphi(j)dis(p_i,p_j)
\end{aligned}
$$
红色的部分可以枚举倍数预处理，复杂度调和级数。于是只要现在考虑怎么求
$$
\sum_{T|i}\sum_{T|j}\varphi(i)\varphi(j)dis(p_i,p_j)
$$
令 $w_{p_i}=\varphi(i)$ ，那么就相当于要求
$$
\sum_{T|i}\sum_{T|j}w_{p_i}w_{p_j}dis_{p_i,p_j}
$$
可以考虑把所有满足 $T|i$ 的 $p_i$ 拿出来建虚树，然后树形 DP 。
设 $dp_u$ 为 $u$ 子树的答案。假设现在要把 $v$ 子树合并到 $u$ 中去（画的似乎有点丑）
那么有
$$
dp_u=dp_u+dp_v+\sum_{i\in U}\sum_{j\in V}w_iw_jdis(i,j)
$$
继续推式子：
$$
\begin{aligned}
&\sum_{i\in U}\sum_{j\in V}w_iw_jdis(i,j)\\
=&\sum_{i\in U}w_i\sum_{j\in V}w_j(dis(i,u)+l+dis(v,j))\\
=&\left(\sum_{i\in U}w_idis(i,u)\sum_{j\in V}w_j\right)+\left(len\sum_{i\in U}w_i\sum_{j\in V}w_j\right)+\left(\sum_{i\in U}w_i\sum_{j\in V}w_jdis(v,j)\right)
\end{aligned}
$$
设
$$
f_u=\sum_{i\in U}w_idis(i,u)\\g_u=\sum_{i\in U}w_i
$$
$f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。
因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。
其实这题写起来挺休闲的
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
for (;b;b>>=1,a=1ll*a*a%mod)
if (b&1) c=1ll*c*a%mod;
return c;
}
int n,p[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
int dep[N],fa[N],sz[N],hson[N],top[N];
int dfn[N],low[N],tim=0;
inline void dfs1(int u,int f) {
dep[u]=dep[fa[u]=f]+1,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==f) continue;
dfs1(v,u),sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
inline void dfs2(int u,int anc) {
dfn[u]=++tim,top[u]=anc;
if (hson[u]) dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
low[u]=tim;
}
inline int getlca(int u,int v) {
while (top[u]!=top[v]) {
if (dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
if (dep[u]<dep[v]) swap(u,v);
return v;
}
inline int getdis(int u,int v) {
return dep[u]+dep[v]-(dep[getlca(u,v)]<<1);
}
int pri[N],v[N],cnt=0;
int mu[N],phi[N],f[N];
inline void sieve() {
mu[1]=phi[1]=1;
for (re int i=2;i<=n;++i) {
if (!v[i]) pri[++cnt]=i,mu[i]=mod-1,phi[i]=i-1;
for (re int j=1;j<=cnt&&i*pri[j]<=n;++j) {
v[i*pri[j]]=1;
if (i%pri[j]) mu[i*pri[j]]=mod-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
}
}
for (re int d=1;d<=n;++d)
for (re int i=d;i<=n;i+=d)
f[i]=(f[i]+1ll*d*qpow(phi[d],mod-2)%mod*mu[i/d]%mod)%mod;
}
namespace VT {
int w[N];
struct edge { int v,w,nxt; } e[N<<1];
int head[N],e_cnt;
inline void addEdge(int u,int v,int w) {
e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt;
}
int seq[N<<1],sta[N<<1];
inline int cmp(int x,int y) { return dfn[x]<dfn[y]; }
inline void build(int d) {
e_cnt=0; int tot=0;
for (re int i=d;i<=n;i+=d) seq[++tot]=p[i],w[p[i]]=phi[i];
sort(seq+1,seq+tot+1,cmp);
for (re int i=tot;i>1;--i) seq[++tot]=getlca(seq[i-1],seq[i]);
seq[++tot]=1;
sort(seq+1,seq+tot+1,cmp),tot=unique(seq+1,seq+tot+1)-seq-1;
for (re int i=1,top=0;i<=tot;++i) {
while (top&&low[sta[top]]<dfn[seq[i]]) --top;
addEdge(sta[top],seq[i],getdis(sta[top],seq[i]));
sta[++top]=seq[i];
}
}
int dp[N],f[N],g[N];
inline void dfs(int u) {
dp[u]=f[u]=0,g[u]=w[u];
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,l=e[i].w; dfs(v);
dp[u]=(dp[u]+dp[v]+1ll*f[u]*g[v]+1ll*g[u]*g[v]%mod*l+1ll*g[u]*f[v])%mod;
f[u]=(f[u]+f[v]+1ll*g[v]*l)%mod,g[u]=(g[u]+g[v])%mod;
}
head[u]=w[u]=0;
}
}
int main() {
n=read(); sieve();
for (re int i=1;i<=n;++i) p[read()]=i;
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs1(1,0),dfs2(1,1); int ans=0;
for (re int i=1;i<=n;++i) {
VT::build(i),VT::dfs(1);
ans=(ans+2ll*f[i]*VT::dp[1])%mod;
}
printf("%lld\n",1ll*qpow(n,mod-2)*qpow(n-1,mod-2)%mod*ans%mod);
return 0;
}