Legend
我们认为树上不同两点 (i,j) 的贡献是 (varphi(a_i imes a_j)dist(i,j))，求随机选两个不同点的期望贡献。
模 (10^9+7)，结点 (le 2 imes 10^5)，保证权值是个排列。
Link ( extrm{to Codeforces})。
Editorial
第一步不难想到，要把 (a_i) 与 (a_j) 分离，怎么分离呢？发现一个式子：(varphi(xy)=frac{varphi(x)varphi(y)gcd(x,y)}{varphi(gcd(x,y))})。
这个式子怎么来的呢？你根据每个质因数考虑一下，就觉得非常有道理了。然后就是要求一个这样的式子：
[egin{aligned}
& sum_{i=1}^{n}sum_{j=1}^{n} frac{varphi(a_i) varphi(a_j)gcd(a_i,a_j)}{varphi(gcd(a_i,a_j))}dist(i,j) \
=& sum_{d=1}^{n}frac{d}{varphi(d)} sum_{i=1}^{n}sum_{j=1}^nvarphi(a_i) varphi(a_j) dist(i,j)[gcd(a_i,a_j)=d] \
=& sum_{d=1}^{n} frac{d}{varphi(d)}sum_{i=1}^{n}sum_{j=1}^{n} varphi(i)varphi(j)[gcd(i,j)=d] imes dist(pos_i,pos_j) \
=& sum_{d=1}^{n} frac{d}{varphi(d)} sum_{i=1}^{lfloor frac{n}{d}
floor} sum_{j=1}^{lfloor frac{n}{d}
floor} varphi(id)varphi(jd)[gcd(i,j)=1] imes dist(pos_{id},pos_{jd}) \
=& sum_{d=1}^{n}frac{d}{varphi(d)} sum_{t=1}^{lfloor frac{n}{d}
floor} mu(t)sum_{i=1}^{lfloor frac{n}{td}
floor}sum_{j=1}^{lfloor frac{n}{td}
floor} varphi(tid)varphi(tjd) imes dist(pos_{tid},pos_{tjd}) \
=& sum_{T=1}^{n} left( sum_{i=1}^{lfloor frac{n}{T}
floor}sum_{j=1}^{lfloor frac{n}{T}
floor}varphi(Ti)varphi(Tj) imes dist(pos_{Ti},pos_{Tj})
ight) imes left( sum_{d|T}frac{dmu(frac{T}{d})}{varphi(d)}
ight)
end{aligned}
]
前面这一截，可以解释为树上两点贡献为 (varphi(a_i)varphi(a_j)dist(i,j))，后面就是个狄利克雷卷积（显然这三个都是积性函数）。
手玩一下 (F(n)=sum_{d|n}frac{dmu(frac{n}{d})}{varphi(d)}) 这个函数在质数的幂下的取值。
| (k) | (0) | (1) | (2) | (3) |
|---|---|---|---|---|
| (F(p^k)) | (1) | (frac{1}{p-1}) | (0) | (0) |
发现出现平方因子的时候答案就是 (0)，质数时为 (frac{1}{p-1})，(1) 时为 (1)。所以可以直接卷了
显然，前面这一截直接快排建虚树按每条边算贡献，是 (O(nlog^2 n)) 的。
然后就做完了，感觉是个缝合题。。
Code
然后你就会发现代码巨长。怎么当年 cf 还能过审这种垃圾题啊
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
#define LL long long
using namespace std;
const int MX = 4e5 + 23;
const LL MOD = 1e9 + 7;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
LL qpow(LL a ,LL b ,LL p = MOD){
LL ans = 1;
while(b){if(b & 1) ans = ans * a % p;
a = a * a % p ,b >>= 1;
}return ans;
}
int head[MX] ,tot = 1;
struct edge{
int node ,next;
}h[MX << 1];
void addedge(int u ,int v ,int flg = 1){
h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
if(flg) addedge(v ,u ,false);
}
namespace FOR_LCA{
int lg2[MX << 1];
// void GetFA(int x); // Get father array of Tree <2>
int rmq(int x ,int y);
int LCA(int x ,int y); // Get LCA(x ,y) of Tree <2>
int dfn[MX] ,cnt ,seq[20][MX << 1] ,seqcnt ,refer[MX];
int dep[MX];
int firstOccurrence[MX];
void init_log2(){
lg2[0] = -1;
for(int i = 1 ; i < MX * 2 ; ++i)
lg2[i] = lg2[i - 1] + (i == (i & -i));
for(int i = 1 ; i <= 19 ; ++i){
for(int j = 1 ; j + (1 << (i - 1)) - 1 <= seqcnt ; ++j){
seq[i][j] = std::min(seq[i - 1][j] ,seq[i - 1][j + (1 << (i - 1))]);
}
}
}
void GetEuler(int x ,int f ,int depth){
seq[0][++seqcnt] = dfn[x] = ++cnt;
firstOccurrence[x] = seqcnt;
refer[cnt] = x;
dep[x] = depth;
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
GetEuler(d ,x ,depth + 1);
seq[0][++seqcnt] = dfn[x];
}
}
int rmq(int l ,int r){
if(l > r) std::swap(l ,r);
int len = lg2[r - l + 1];
return std::min(seq[len][l] ,seq[len][r - (1 << len) + 1]);
}
int LCA(int l ,int r){return refer[rmq(firstOccurrence[l] ,firstOccurrence[r])];}
int dis(int x ,int y){return dep[x] + dep[y] - 2 * dep[LCA(x ,y)];}
void Main(){
GetEuler(1 ,0 ,1);
init_log2();
}
}
using FOR_LCA::LCA;
using FOR_LCA::dis;
LL F[MX] ,phi[MX];
int npri[MX] ,pri[MX] ,qwq;
void init(){
npri[0] = npri[1] = 1 ,phi[1] = F[1] = 1;
for(int i = 2 ; i < MX ; ++i){
if(!npri[i]){
pri[++qwq] = i;
F[i] = qpow(i - 1 ,MOD - 2);
phi[i] = i - 1;
}
for(int j = 1 ; j <= qwq && pri[j] * i < MX ; ++j){
int aim = pri[j] * i;
npri[aim] = 1;
if(i % pri[j] == 0){
phi[aim] = phi[i] * pri[j];
F[aim] = 0;
break;
}
phi[aim] = phi[i] * phi[pri[j]];
F[aim] = F[i] * F[pri[j]] % MOD;
}
}
}
int n ,a[MX] ,pos[MX];
int app[2][MX] ,appcnt;
void GetOrder(int x ,int f){
app[0][x] = ++appcnt;
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
GetOrder(d ,x);
}
app[1][x] = ++appcnt;
}
struct POINT{
int id ,tim;
bool operator <(const POINT& B)const{
return tim < B.tim;
}
}S[MX << 1];
int Suse[MX] ,Scnt;
void addPOINT(int x){
if(Suse[x]++) return;
++Scnt ,S[Scnt] = (POINT){x ,app[0][x]};
++Scnt ,S[Scnt] = (POINT){-x ,app[1][x]};
}
int stk[MX] ,stktop;
LL size[MX];
LL solve(int T){
LL all = 0;
for(int i = T ; i <= n ; i += T){
addPOINT(pos[i]);
all = (all + phi[i]) % MOD;
}
std::sort(S + 1 ,S + 1 + Scnt);
int curScnt = Scnt;
for(int i = 1 ; i < curScnt ; ++i){
addPOINT(LCA(abs(S[i].id) ,abs(S[i + 1].id)));
}
addPOINT(1);
std::sort(S + 1 ,S + 1 + Scnt);
LL ans = 0;
for(int i = 1 ; i <= Scnt ; ++i){
int x = abs(S[i].id);
if(S[i].id > 0){
stk[++stktop] = x;
size[x] = (a[x] % T == 0) * phi[a[x]];
}
else{
--stktop;
if(stktop){
// debug("%d
" ,stk[stktop]);
(size[stk[stktop]] += size[x]) %= MOD;
ans = (ans + (all - size[x] + MOD) * size[x] % MOD * dis(x ,stk[stktop])) % MOD;
}
Suse[x] = false;
}
}
ans = ans * F[T] % MOD;
Scnt = 0;
return ans;
}
int main(){
init();
n = read();
for(int i = 1 ; i <= n ; ++i) pos[a[i] = read()] = i;
for(int i = 2 ,u ,v ; i <= n ; ++i){
u = read() ,v = read();
addedge(u ,v);
}
FOR_LCA::Main();
GetOrder(1 ,0);
LL ans = 0;
for(int i = 1 ; i <= n / 2 ; ++i) ans = (ans + solve(i)) % MOD;
ans = ans * qpow(1LL * n * (n - 1) % MOD ,MOD - 2) % MOD * 2 % MOD;
printf("%lld
" ,ans);
return 0;
}