【题解】Surprise me! 莫比乌斯反演，虚树 CF809E

for test

Solution

让 $D_i$ 表示 $a_x$ 为 $i$ 的 $x$。

$ans = \frac{1}{n(n – 1)} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} dist(D_i, D_j) \varphi(ij)$

考虑 P4240 毒瘤之神的考验 的某个结论 (其实很好证明，这里不展开来证明了 qwq）: $\varphi(ij) = \frac{\varphi(i) \varphi(j) \gcd(i, j)}{\varphi(\gcd(i, j))}$

$\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} dist(D_i, D_j) \varphi(ij)$

$= \sum\limits_{i = 1}^{n}\varphi(i) \sum\limits_{j = 1}^{n} \varphi(j) \frac{\gcd(i, j)}{\varphi(\gcd(i, j))} dist(D_i, D_j)$

$= \sum\limits_{d = 1}^{n} \frac{d}{\varphi(d)} \sum\limits_{i = 1}^{\frac{n}{d}}\varphi(id) \sum\limits_{j = 1}^{\frac{n}{d}} \varphi(jd) dist(D_{id}, D_{jd}) [\gcd(i, j) = 1]$

$= \sum\limits_{d = 1}^{n} \frac{d}{\varphi(d)} \sum\limits_{p = 1}^{\frac{n}{p}} \mu(p) \sum\limits_{i = 1}^{\frac{n}{dp}}\varphi(idp) \sum\limits_{j = 1}^{\frac{n}{dp}} \varphi(jdp) dist(D_{idp}, D_{jdp})$

$= \sum\limits_{L = 1}^{n} \sum\limits_{d | L} \frac{d}{\varphi(d)} \mu(\frac{L}{p}) \sum\limits_{i = 1}^{\frac{n}{L}}\varphi(iL) \sum\limits_{j = 1}^{\frac{n}{L}} \varphi(jL) dist(D_{iL}, D_{jL})$

设 $g(L) = \sum\limits_{d | L} \frac{d}{\varphi(d)} \mu(\frac{L}{p})$

$\sum\limits_{L = 1}^{n} g(L) \sum\limits_{i = 1}^{\frac{n}{L}}\varphi(iL) \sum\limits_{j = 1}^{\frac{n}{L}} \varphi(jL) dist(D_{iL}, D_{jL})$

让 $S$ 为值是 $d$ 的倍数的点，对于一个 $d$ 的计算 :

$\sum\limits_{x \in S} \sum\limits_{y \in S} \varphi(a_x) \varphi(a_y) dist(x, y)$

$\sum\limits_{x \in S} \sum\limits_{y \in S} \varphi(a_x) \varphi(a_y) (dep_x + dep_y – 2dep_{LCA})$

$2 \sum\limits_{x \in S} \varphi(a_x) dep_x \sum\limits_{y \in S} \varphi(a_y) – 2\sum\limits_{LCA \in S} dep_{LCA}\sum\limits_{x, y \in S, lca(x, y) = LCA} \varphi(a_x) \varphi(a_y)$

建个虚树 $dp$ 就完了