这是一道神仙题
看到这样一个鬼畜的柿子
[sum_{i=1}^nsum_{j=1}^nvarphi(a_i imes a_j) imes dis(i,j)
]
又是树上距离又是(varphi)的看起来根本就不知道怎么搞啊
首先需要知道一个这样的性质
[varphi(a imes b)=frac{varphi(a) imes varphi(b) imes d}{varphi(d)},d=(a,b)
]
这个性质非常显然
设(a=p^{k_1},b=p^{k_2},k_1<k_2)
于是(d=p^{k_1})
[varphi(a imes b)=varphi(p^{k_1+k_2})=p^{k_1+k_2-1}(p-1)
]
[frac{varphi(a) imes varphi(b) imes d}{varphi(d)}=frac{p^{k_1-1}p^{k_2-1}(p-1)^2p^{k_1}}{p^{k_1-1}(p-1)}=p^{k_1+k_2-1}(p-1)
]
这个东西显然是积性的，扩展到多个质因子也是成立的
于是写成
[sum_{i=1}^nsum_{j=1}^nfrac{varphi(a_i) imes varphi(a_j) imes (a_i,a_j)}{varphi((a_i,a_j))} imes dis(i,j)
]
套路枚举(gcd)
[sum_{d=1}^nfrac{d}{varphi(d)}sum_{i=1}^nsum_{j=1}^n[(a_i,a_j)=d]varphi(a_i) imes varphi(a_j) imes dis(i,j)
]
考虑设后面那个东西叫
[f(d)=sum_{i=1}^nsum_{j=1}^n[(a_i,a_j)=d]varphi(a_i) imes varphi(a_j) imes dis(i,j)
]
显然我们还需要一个函数叫
[F(d)=sum_{i=1}^nsum_{j=1}^n[d|(a_i,a_j)]varphi(a_i) imes varphi(a_j) imes dis(i,j)
]
我们可以直接反演了
[F(d)=sum_{d|n}f(n)
]
[f(d)=sum_{d|n}mu(frac{n}{d})F(n)
]
现在的问题就是求出(F)，我们就可以做了
显然树上的点都有一个约数(d)的时候，任意两点的的(gcd)就会是(d)的倍数
我们如果把(d|a_i)的(i)拿出来，建出一棵虚树，搞一个树形(dp)
求一下
[dp_i=sum_{j=1}^ndis(i,j)varphi(a_j)
]
就好了，这就是一个小学生(dp)求树上带权重心了
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
const int maxn=2e5+5;
const LL mod=1e9+7;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt,w;}e[maxn<<1];
int dfn[maxn],son[maxn],deep[maxn],a[maxn],b[maxn],P[maxn];
int Top[maxn],st[maxn],num,n,__,top,head[maxn],fa[maxn];
int f[maxn],p[maxn>>1],mu[maxn],phi[maxn];
LL dp[maxn],sum[maxn],S,inv[maxn],F[maxn];
inline int cmp(int a,int b) {return dfn[a]<dfn[b];}
inline LL ksm(LL a,int b) {
LL S=1;
while(b) {if(b&1) S=S*a%mod;b>>=1;a=a*a%mod;}
return S;
}
inline void add(int x,int y,int w) {
e[++num].v=y;e[num].nxt=head[x];
head[x]=num;e[num].w=w;
}
void dfs1(int x) {
int maxx=-1;sum[x]=1;
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]) continue;
deep[e[i].v]=deep[x]+1,fa[e[i].v]=x;
dfs1(e[i].v);sum[x]+=sum[e[i].v];
if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;
}
}
void dfs2(int x,int topf) {
Top[x]=topf;dfn[x]=++__;
if(!son[x]) return;
dfs2(son[x],topf);
for(re int i=head[x];i;i=e[i].nxt)
if(!Top[e[i].v]) dfs2(e[i].v,e[i].v);
}
inline int LCA(int x,int y) {
while(Top[x]!=Top[y]) {
if(deep[Top[x]]<deep[Top[y]]) std::swap(x,y);
x=fa[Top[x]];
}
if(deep[x]<deep[y]) return x;return y;
}
inline void ins(int x) {
if(top<=1) {st[++top]=x;return;}
int lca=LCA(st[top],x);
if(lca==st[top]) {st[++top]=x;return;}
while(top>1&&dfn[st[top-1]]>=dfn[lca])
add(st[top-1],st[top],deep[st[top]]-deep[st[top-1]]),top--;
if(lca!=st[top]) {add(lca,st[top],deep[st[top]]-deep[lca]);st[top]=lca;}
st[++top]=x;
}
void dfs(int x) {
sum[x]=f[x]*phi[a[x]];
for(re int i=head[x];i;i=e[i].nxt) {
dfs(e[i].v);
sum[x]+=sum[e[i].v];
dp[x]+=(dp[e[i].v]+sum[e[i].v]*(LL)e[i].w%mod)%mod;
dp[x]%=mod;
}
}
void reDfs(int x) {
for(re int i=head[x];i;i=e[i].nxt) {
LL now=dp[x]-(dp[e[i].v]+sum[e[i].v]*(LL)e[i].w%mod)%mod;
now=(now+mod)%mod;
dp[e[i].v]=(dp[e[i].v]+now+((S-sum[e[i].v])*(LL)e[i].w)%mod)%mod;
reDfs(e[i].v);
}
}
void clear(int x) {
f[x]=dp[x]=sum[x]=0;
for(re int i=head[x];i;i=e[i].nxt) clear(e[i].v);
head[x]=0;
}
int main() {
n=read();
for(re int i=1;i<=n;i++) a[i]=read();
for(re int x,y,i=1;i<n;i++)
x=read(),y=read(),add(x,y,0),add(y,x,0);
deep[1]=1,dfs1(1),dfs2(1,1);
for(re int i=1;i<=n;i++) b[a[i]]=i;
f[1]=mu[1]=phi[1]=1;
for(re int i=2;i<=n;i++) {
if(!f[i]) p[++p[0]]=i,mu[i]=-1,phi[i]=i-1;
for(re int j=1;j<=p[0]&&p[j]*i<=n;j++) {
f[p[j]*i]=1;
if(i%p[j]==0) {
phi[p[j]*i]=p[j]*phi[i];
break;
}
mu[p[j]*i]=-1*mu[i];
phi[p[j]*i]=(p[j]-1)*phi[i];
}
}
inv[1]=1;
for(re int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
memset(sum,0,sizeof(sum));
for(re int k=1;k<=n;k++) {
int tot=0;
num=0,top=0;
for(re int j=k;j<=n;j+=k)
P[++tot]=b[j],f[P[tot]]=1;
std::sort(P+1,P+tot+1,cmp);
int rt=P[1];
for(re int i=2;i<=tot;i++) rt=LCA(rt,P[i]);
if(!f[rt]) st[++top]=rt;
for(re int i=1;i<=tot;i++) ins(P[i]);
while(top) add(st[top-1],st[top],deep[st[top]]-deep[st[top-1]]),top--;
dfs(rt);S=sum[rt];reDfs(rt);
for(re int i=1;i<=tot;i++)
F[k]=(F[k]+(LL)phi[a[P[i]]]*dp[P[i]]%mod)%mod;
clear(rt);
}
LL ans=0;
for(re int i=1;i<=n;i++) {
LL now=0;
for(re int j=i;j<=n;j+=i)
now=(now+F[j]*mu[j/i]%mod)%mod,now=(now+mod)%mod;
ans=(ans+now*(LL)i%mod*inv[phi[i]]%mod)%mod;
}
LL now=(LL)n*(LL)(n-1);
now%=mod;
printf("%lld
",ksm(now,mod-2)*ans%mod);
return 0;
}