题解：
一道很套路的题目
首先一个结论
$\phi(xy)=\frac{\phi(x)*\phi(y)*gcd(x,y)}{\phi(gcd(x,y))}$
这个按照$\phi$的定义很容易知道
然后我们可以枚举gcd，很套路的可以莫比乌斯反演
然后变成给出k个点，求他们$\phi(x)*\phi(y)*dis(x,y)$
考虑所以gcd的点数为$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}$=$nlogn$
于是我们需要一个与点数相关的算法
考虑虚树
之后有两种办法解决$\phi(x)*\phi(y)*dis(x,y)$
一种是考虑一个节点和它儿子节点的关系，那么就处理一下子树信息就行了
一种是把$dis(x,y)$写成$dis(x)+dis(y)-2*dis(lca(x,y))$然后dp一下
代码：
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
const int N=5e5;
const int mo=1e9+;
int a[N],head[N],dfn[N],cnt,p[N],pos[N],q[N],bz[][N],dep[N];
int f[N],phi[N],pri[N],prinum,ispri[N],n,l,miu[N],inv2;
bool tt[N];
struct re{
int a,b,c;
}e[N*];
int fsp(int x,int y)
{
ll ans=;
while (y)
{
if (y&) ans=ans*x%mo;
x=1ll*x*x%mo; y>>=;
}
return ans;
}
IL void plu(int &x,int y)
{
x=(x+y)%mo;
}
IL void arr(int x,int y)
{
e[++l].a=head[x];
e[l].b=y;
head[x]=l;
}
void dfs(int x,int y)
{
dfn[x]=++cnt; bz[][x]=y; dep[x]=dep[y]+;
for (rint u=head[x];u;u=e[u].a)
{
int v=e[u].b;
if (v!=y) dfs(v,x);
}
}
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
dep(i,,) if (dep[bz[i][x]]>=dep[y]) x=bz[i][x];
if (x==y) return x;
dep(i,,) if (bz[i][x]!=bz[i][y]) x=bz[i][x],y=bz[i][y];
return bz[][x];
}
ll pp;
struct E{
int l,head[N],ans[N];
re e[N*];
IL void arr(int x,int y)
{
e[++l].a=head[x];
e[l].b=y;
e[l].c=x;
head[x]=l;
}
IL void clear()
{
rep(i,,l) head[e[i].c]=;
l=;
}
void dfs(int x)
{
ans[x]=phi[a[x]];
if (!tt[x])
{
ans[x]=;
}
ll ans2=;
for (rint u=head[x];u;u=e[u].a)
{
int v=e[u].b;
dfs(v);
ans[x]=(ans[x]+ans[v])%mo;
ans2+=1ll*ans[v]*ans[v];
}
ans2=(1ll*ans[x]*ans[x]-ans2)%mo;
pp=(pp+*dep[x]*ans2)%mo;
}
}E;
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
rep(i,,n) cin>>a[i],pos[a[i]]=i;
rep(i,,n-)
{
int x,y;
cin>>x>>y;
arr(x,y); arr(y,x);
}
dfs(,);
rep(i,,)
rep(j,,n)
bz[i][j]=bz[i-][bz[i-][j]];
miu[]=; phi[]=;
rep(i,,n)
{
if (!ispri[i]) {pri[++prinum]=i; miu[i]=-; phi[i]=i-;}
for (int j=;j<=prinum&&pri[j]*i<=n;j++)
{
ispri[i*pri[j]]=;
if (i%pri[j]==)
{
miu[i*pri[j]]=;
phi[i*pri[j]]=phi[i]*pri[j];
break;
} else miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*(pri[j]-);
}
}
rep(i,,n)
{
int num=;
int ans=;
ll ans2=;
for (int j=;j*i<=n;j++) p[++num]=pos[i*j],plu(ans,phi[i*j]);
rep(j,,num) ans2=(ans2+1ll*phi[i*j]*dep[p[j]])%mo;
ans2=2ll*ans2*ans%mo;
sort(p+,p+num+,cmp);
rep(i,,num) tt[p[i]]=;
int h=,t=; q[h]=;
rep(i,,num)
{
while (h<t&&dep[lca(p[i],q[t])]<=dep[q[t-]])
{
E.arr(q[t-],q[t]); t--;
}
int k=lca(p[i],q[t]);
if (k!=q[t])
{
E.arr(k,q[t]); q[t]=k;
}
if (q[t]!=p[i]) q[++t]=p[i];
}
while (h<t)
{
E.arr(q[t-],q[t]); t--;
}
pp=;
E.dfs();
ans2=((ans2-pp)%mo+mo)%mo;
f[i]=ans2;
E.clear();
rep(i,,num) tt[p[i]]=;
}
ll ans2=;
rep(k,,n)
{
int ans=;
for (int j=;j*k<=n;j++)
{
plu(ans,miu[j]*f[j*k]);
}
ans2=(ans2+1ll*k*ans%mo*fsp(phi[k],mo-))%mo;
}
cout<<ans2*fsp(n,mo-)%mo*fsp(n-,mo-)%mo<<endl;
return ;
}