【Codeforces809E】Surprise me

发表于
https://codeforces.com/problemset/problem/809/E

题目链接

【Codeforces809E】Surprise me

做法

已知 $ \phi(xy) = \frac{ \phi(x) \phi(y) \gcd(x, y) }{ \phi(gcd(x, y)) } $
代入并莫比乌斯反演得：
$$ n(n - 1) Ans = \sum_{ T = 1 }^{ n } \sum_{ d | T } \frac{ d \mu(\frac{ T }{ d }) }{ \phi(d) } \sum_{ d | a_i } \sum_{ d | a_j } \phi(a_i) \phi(a_j) dist(i, j) $$
发现 $ \sum_{ T = 1 }^{ n } \sum_{ d | T } \frac{ d \mu(\frac{ T }{ d }) }{ \phi(d) } $ 可以调和级数， $ \sum_{ d | a_i } \sum_{ d | a_j } \phi(a_i) \phi(a_j) dist(i, j) $ 建的虚树点数总数也是调和级数。
可以用 RMQ_LCA 实现复杂度 $ O(n \log n) $ 。
作为一个懒汉我写树剖LCA。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 200010, mod = 1e9 + 7;
int n, a[N], id[N], inv[N], ans = 0;
int p[N], mu[N], phi[N], lp; bool pri[N];
vector<int> e[N], E[N];
int fa[N], sz[N], son[N], dep[N], top[N], dfn[N], idx = 0;
int s[N], f[N], g[N], ss[N];
int pp[N], len, sta[N], Top = 0;
bool flag[N];

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }
inline bool cmp(const int &x, const int &y) { return dfn[x] < dfn[y]; }
void Sieve() {
	inv[0] = inv[1] = 1, phi[1] = mu[1] = 1;
	for(int i = 2; i <= n; i++) inv[i] = mul(mod - mod / i, inv[mod % i]);
	for(int i = 2; i <= n; i++) {
		if(!pri[i]) p[++lp] = i, mu[i] = mod - 1, phi[i] = i - 1;
		for(int j = 1; p[j] * i <= n; j++) {
			pri[p[j] * i] = 1;
			if(i % p[j] == 0) { phi[p[j] * i] = phi[i] * p[j]; break; }
			mu[p[j] * i] = sub(0, mu[i]);
			phi[p[j] * i] = phi[i] * (p[j] - 1);
		}
	}
	for(int i = 1; i <= n; i++) for(int j = i; j <= n; j += i)
		s[j] = add(s[j], mul(mul(i, mu[j / i]), inv[phi[i]]));
}
void dfs1(int u, int ff) {
	fa[u] = ff, dep[u] = dep[ff] + 1, sz[u] = 1;
	for(auto v : e[u]) if(v ^ ff) {
		dfs1(v, u), sz[u] += sz[v]; if(sz[son[u]] < sz[v]) son[u] = v;
	}
}
void dfs2(int u, int tp) {
	top[u] = tp, dfn[u] = ++idx; if(son[u]) dfs2(son[u], tp);
	for(auto v : e[u]) if(!top[v]) dfs2(v, v);
}
int LCA(int x, int y) {
	for(; top[x] != top[y]; x = fa[top[x]])
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
	return dep[x] < dep[y] ? x : y;
}
void insert(int x) {
	int lca = LCA(x, sta[Top]);
	if(Top == 1 || lca == sta[Top]) { sta[++Top] = x; return ; }
	for(; Top > 1 && dfn[sta[Top - 1]] >= dfn[lca]; --Top)
		E[sta[Top - 1]].pb(sta[Top]);
	if(lca != sta[Top]) E[lca].pb(sta[Top]), sta[Top] = lca;
	sta[++Top] = x;
}
void dp(int u) {
	ss[u] = flag[u] * phi[a[u]], f[u] = g[u] = 0;
	for(auto v : E[u]) {
		dp(v); int w = dep[v] - dep[u];
		g[u] = add(g[v], add(add(g[u], mul(ss[v], add(mul(w, ss[u]), f[u]))), mul(ss[u], f[v])));
		ss[u] = add(ss[u], ss[v]), f[u] = add(f[u], add(f[v], mul(ss[v], w)));
	}
	E[u].clear(), flag[u] = 0;
}
int calc(int x) {
	len = 0; for(int i = x; i <= n; i += x) pp[++len] = id[i];
	sort(pp + 1, pp + len + 1, cmp), sta[Top = 1] = 1;
	for(int i = 1; i <= len; i++) {
		flag[pp[i]] = 1; if(pp[i] != 1) insert(pp[i]);
	}
	for(; Top > 1; --Top) E[sta[Top - 1]].pb(sta[Top]);
	dp(1); return g[1];
}
int main() {
	scanf("%d", &n), Sieve();
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), id[a[i]] = i;
	for(int i = 1, x, y; i < n; i++)
		scanf("%d%d", &x, &y), e[x].pb(y), e[y].pb(x);
	dfs1(1, 0), dfs2(1, 1);
	for(int i = 1; i <= n; i++) ans = add(ans, mul(calc(i), s[i]));
	printf("%d\n", mul(add(ans, ans), mul(inv[n], inv[n - 1])));
	return 0;
}