Legend

我们认为树上不同两点 \(i,j\) 的贡献是 \(\varphi(a_i\times a_j)dist(i,j)\)，求随机选两个不同点的期望贡献。

模 \(10^9+7\)，结点 \(\le 2\times 10^5\)，保证权值是个排列。

Link \(\textrm{to Codeforces}\)。

Editorial

\[\begin{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}^n\varphi(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]\times dist(pos_i,pos_j) \\ =& \sum_{d=1}^{n} \frac{d}{\varphi(d)} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} \varphi(id)\varphi(jd)[gcd(i,j)=1]\times dist(pos_{id},pos_{jd}) \\ =& \sum_{d=1}^{n}\frac{d}{\varphi(d)} \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t)\sum_{i=1}^{\lfloor \frac{n}{td} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{td} \rfloor} \varphi(tid)\varphi(tjd)\times dist(pos_{tid},pos_{tjd}) \\ =& \sum_{T=1}^{n} \left( \sum_{i=1}^{\lfloor \frac{n}{T} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{T} \rfloor}\varphi(Ti)\varphi(Tj) \times dist(pos_{Ti},pos_{Tj}) \right) \times \left( \sum_{d|T}\frac{d\mu(\frac{T}{d})}{\varphi(d)} \right) \end{aligned} \]

前面这一截，可以解释为树上两点贡献为 \(\varphi(a_i)\varphi(a_j)dist(i,j)\)，后面就是个狄利克雷卷积（显然这三个都是积性函数）。

手玩一下 \(F(n)=\sum_{d|n}\frac{d\mu(\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(n\log^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\n" ,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\n" ,ans);
	return 0;
}