题面
题解
这道题目的话，推式子比较休闲，写起来。。。
首先上套路，根据(varphi)的一些性质，我们可以证明(varphi(ij) = frac{varphi(i)varphi(j)gcd(i, j)}{varphi(gcd(i,j))})。
开推：首先设( extbf{f}(x) = frac x {varphi(x)}, extbf g = extbf f * mu, p_{a_i} = i)，
那么有（我的这种推法是学的rqy的比较简单的，建议参阅）：
[egin{aligned}
&sum_{i=1}^nsum_{j=1}^nvarphi(a_i*a_j)cdot mathrm{dist}(i,j) \
=& sum_{i=1}^nsum_{j=1}^nvarphi(i)varphi(j)mathrm{dist}(p_i, p_j) extbf f(gcd(i,j)) \
=& sum_{i=1}^nsum_{j=1}^nvarphi(i)varphi(j)mathrm{dist}(p_i, p_j)sum_{dmid i, dmid j} extbf g(d) \
=& sum_{d=1}^n extbf g(d)sum_{dmid i}sum_{dmid j}varphi(i)varphi(j)mathrm{dist}(p_{i},p_{j})
end{aligned}
]
( extbf g)可以枚举倍数求，复杂度调和级数。
然后后面那一坨可以枚举倍数，将所有是(d)的倍数的点全部拉出来建一棵虚树，做一遍树形(mathrm{dp})就可以了。
虚树的总点数在(mathrm{O}(nlog n))级别，所以总复杂度约为(mathrm{O}(nlog^2n))
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define clear(x, y) memset(x, y, sizeof(x))
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(2e5 + 10), Mod(1e9 + 7);
int fastpow(int x, int y)
{
int ans = 1;
for(; y; y >>= 1, x = 1ll * x * x % Mod)
if(y & 1) ans = 1ll * ans * x % Mod;
return ans;
}
namespace Numbers
{
int prime[maxn], cnt, mu[maxn], phi[maxn], not_prime[maxn], iphi[maxn];
void Init(int n)
{
mu[1] = phi[1] = not_prime[1] = 1;
for(RG int i = 2; i <= n; i++)
{
if(!not_prime[i]) prime[++cnt] = i, phi[i] = i - 1, mu[i] = Mod - 1;
for(RG int j = 1; j <= cnt && i * prime[j] <= n; j++)
{
not_prime[i * prime[j]] = 1;
if(i % prime[j]) mu[i * prime[j]] = Mod - mu[i],
phi[i * prime[j]] = phi[i] * phi[prime[j]];
else { phi[i * prime[j]] = phi[i] * prime[j]; break; }
}
}
for(RG int i = 1; i <= n; i++)
iphi[i] = fastpow(phi[i], Mod - 2);
}
}
namespace Vtree
{
struct edge { int next, to, dis; } e[maxn << 1];
int head[maxn], e_num, fa[maxn], size[maxn], heavy[maxn], stk[maxn << 1];
int pos[maxn], end_pos[maxn], belong[maxn], cnt, p[maxn << 1], K, dep[maxn];
inline void add_edge(int from, int to, int dis = 0)
{
e[++e_num] = (edge) {head[from], to, dis};
head[from] = e_num;
}
void dfs(int x)
{
size[x] = 1;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa[x]) continue;
fa[to] = x, dep[to] = dep[x] + 1; dfs(to); size[x] += size[to];
if(size[heavy[x]] < size[to]) heavy[x] = to;
}
}
void dfs(int x, int chain)
{
belong[x] = chain, pos[x] = ++cnt;
if(heavy[x]) dfs(heavy[x], chain);
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to;
if(to == fa[x] || to == heavy[x]) continue;
dfs(to, to);
}
end_pos[x] = cnt;
}
int LCA(int x, int y)
{
for(; belong[x] != belong[y]; x = fa[belong[x]])
if(pos[belong[x]] < pos[belong[y]]) std::swap(x, y);
return pos[x] < pos[y] ? x : y;
}
int Dis(int x, int y) { return dep[x] + dep[y] - 2 * dep[LCA(x, y)]; }
inline bool cmp(int x, int y) { return pos[x] < pos[y]; }
void build()
{
e_num = 0; std::sort(p + 1, p + K + 1, cmp);
for(RG int i = K; i > 1; i--) p[++K] = LCA(p[i], p[i - 1]);
p[++K] = 1; std::sort(p + 1, p + K + 1, cmp);
K = std::unique(p + 1, p + K + 1) - p - 1;
for(RG int i = 1, top = 0; i <= K; i++)
{
while(top && end_pos[stk[top]] < pos[p[i]]) --top;
add_edge(stk[top], p[i], Dis(stk[top], p[i])); stk[++top] = p[i];
}
}
}
int f[maxn], g[maxn], s[maxn], a[maxn], b[maxn], c[maxn];
void dfs(int x)
{
f[x] = g[x] = 0, s[x] = b[x];
for(RG int i = Vtree::head[x]; i; i = Vtree::e[i].next)
{
int to = Vtree::e[i].to, dis = Vtree::e[i].dis; dfs(to);
g[x] = (((g[x] + g[to]) % Mod + 1ll * s[to] * (f[x] +
1ll * s[x] * dis % Mod) % Mod) % Mod
+ 1ll * f[to] * s[x] % Mod) % Mod;
s[x] = (s[x] + s[to]) % Mod;
f[x] = ((f[x] + f[to]) % Mod + 1ll * s[to] * dis % Mod) % Mod;
}
Vtree::head[x] = 0, b[x] = 0;
}
int n;
int main()
{
n = read();
for(RG int i = 1; i <= n; i++) a[read()] = i;
for(RG int i = 1, x, y; i < n; i++)
x = read(), y = read(), Vtree::add_edge(x, y), Vtree::add_edge(y, x);
Vtree::dfs(1); Vtree::dfs(1, 1); memset(Vtree::head, 0, sizeof Vtree::head);
Numbers::Init(n); using Numbers::mu; using Numbers::iphi;
for(RG int d = 1; d <= n; d++)
for(RG int i = d; i <= n; i += d)
c[i] = (c[i] + 1ll * d * mu[i / d] % Mod * iphi[d] % Mod) % Mod;
int ans = 0;
for(RG int i = 1; i <= n; i++)
{
Vtree::K = 0;
for(RG int j = i; j <= n; j += i)
Vtree::p[++Vtree::K] = a[j],
b[a[j]] = Numbers::phi[j];
Vtree::build(); dfs(1);
ans = (ans + 2ll * c[i] * g[1] % Mod) % Mod;
}
ans = 1ll * ans * fastpow(n, Mod - 2) % Mod * fastpow(n - 1, Mod - 2) % Mod;
printf("%d
", ans);
return 0;
}