夏晓光(loveJY)的博客

首先我们需要知道一个这样的性质：

$\phi(ab)=\frac{\phi(a)\phi(b)\gcd(a,b)}{\phi(\gcd(a,b))}$

我：？？？

这个由$\phi(n)=n\prod_{p}(1-\frac{1}{p})$容易验证

这样有啥好处呢？我们就召唤出了反演中最喜欢的gcd！

然后我们套路地枚举个gcd召唤个mu，枚举$t=g*d$

然后就可以推出这样的柿子：

$\sum_{t=1}^n\sum_{d|t}\frac{d*\mu(\frac{t}{d})}{\phi(d)}\sum_{i=1}^{\frac{n}{t}}\sum_{j=1}^{\frac{n}{t}}\phi(it)\phi(jt)dis(pos[it],pos[jt])$

其中$pos[i]$表示权值为i的是第几个点，即pos[a[i]]=i;

然后，可以发现前后两部分并没有关系

$\sum_{t=1}^n\big(\sum_{d|t}\frac{d*\mu(\frac{t}{d})}{\phi(d)}\big)\big(\sum_{i=1}^{\frac{n}{t}}\sum_{j=1}^{\frac{n}{t}}\phi(it)\phi(jt)dis(pos[it],pos[jt])\big)$

可以令$g(t)=\sum_{d|t}\frac{d*\mu(\frac{t}{d})}{\phi(d)}$，直接$n\ln n$预处理即可。

令$f(t)=\sum_{i=1}^{\frac{n}{t}}\sum_{j=1}^{\frac{n}{t}}\phi(it)\phi(jt)dis(pos[it],pos[jt])$

然后不太好弄，我们把dis拆开

$f(t)=\sum_{i=1}^{\frac{n}{t}}\sum_{j=1}^{\frac{n}{t}}\phi(it)\phi(jt)(dep[pos[it]]+dep[pos[jt]]-2*dep[lca])$

拆开

$f(t)=\sum_{i=1}^{\frac{n}{t}}\sum_{j=1}^{\frac{n}{t}}\phi(it)\phi(jt)dep[pos[it]]+\phi(it)\phi(jt)dep[pos[jt]]-2*\phi(it)\phi(jt)dep[lca]$

可以发现前两项是相同的，可以$O(\frac{n}{t})$处理。

具体来说是整成这样：($\sum_{i=1}^{\frac{n}{t}}\phi(it)dep[pos[it]])(\sum_{i=1}^{\frac{n}{t}}\phi(it))$

然后后面那部分$f(t)=2*\sum_{i=1}^{\frac{n}{t}}\sum_{j=1}^{\frac{n}{t}}\phi(it)\phi(jt)dep[lca(pos[it],pos[jt])]$

然后我们把所有pos[it] (pos[jt]一样)拿出来建虚树，一共不会超过$n\ln n$个点

然后像这道题一样，在lca处一个一个子树合并（别忘了考虑他自己和自己及子树内点的lca也是他自己），就可以做了！（别忘了虚树中只有关键点的phi计入）

反正大概就是$x1*y1+x2*y1+x3*y1+x1*y2+x2*y2+x3*y2+x3*y1+x1*y3+x2*y3+x3*y3=(x1+x2+x3)(y1+y2+y3)$这种，于是维护子树内关键点的phi值和，然后再乘上自己的dep就可以了。

Finished! by zhqwq