闲话9.4
今天终于没有摆一天了。
今天上午把昨天晚上剩的一道题写了写，然后补了补期望😭😭😭，期望啥都不会了😨😨😨
下午听 llx 讲组合数学😋😋😋，收获很多😍😍😍
晚上瞎几把写题，收获很多🤗🤗🤗
好消息：把博客搞到 netlify 上了，评论功能也不用挂梯子喽！
更好消息：发现 netlify.net 是黄色网站
另报：给博客搞上了页面内播放器，舒服😍😍😍
逆天姬芈
jimmy：你这个 main 函数为什么是 signed 类型的啊
jimmy：我还是推荐大家用一些 c++ 标准的写法啊
jimmy：你这个不标准的写法考试的时候可能吃大亏
不好评价
又被 haosen D 了😭😭😭
记录经典
推歌：デザイアドライブ -上海アリス幻樂団
欲望加速。虽然之前没怎么听过（就打过一次庙），但是看 B 站的时候看到有人提到，正好逛正作原曲的时候看到了这首，听了下发现是真的好听！
CF809E
比较套路的题。
我们先把 \(\varphi(a_ia_j)\) 转化为 \(\frac{\varphi (a_i)\varphi (a_j)}{\varphi (\gcd (a_i, a_j))}\)。然后我们大力推式子：
\[\sum \limits_{i=1}^n \sum \limits_{j=1}^n \frac{\varphi (a_i)\varphi (a_j)}{\varphi (\gcd (a_i, a_j))}dist(i, j)
\]
我们先枚举 \(\gcd\)，我们就能得到：
\[\begin{aligned}
\sum_{d=1}^n \frac{1}{\varphi(d)} \sum \limits_{i=1}^n \sum \limits_{j=1}^n \varphi (a_i)\varphi (a_j)dist(i, j)[\gcd(a_i, a_j)=d]
\end{aligned}
\]
我们直接使用莫反套路，把 \([\gcd(i, j)=d]\) 变为 \([\gcd(i, j)|d]\)，得到：
\[\begin{aligned}
\sum_{d=1}^n \frac{1}{\varphi(d)} \sum \limits_{i=1}^n \sum \limits_{j=1}^n \varphi (a_i)\varphi (a_j)dist(i, j)[\gcd(a_i, a_j)|d]
\end{aligned}
\]
我们把所有是 \(d\) 倍数的点扣下来建个虚树，中括号就能消掉。然后就考虑 dp 求出这一坨。
\[\begin{aligned}
\sum \limits_{i=1}^m \sum \limits_{j=1}^m \varphi (a_i)\varphi (a_j)dist(i, j)&=\frac{1}{\varphi(d)} \sum \limits_{i=1}^m \sum \limits_{j=1}^m \varphi (a_i)\varphi (a_j)(dep_i+dep_j-2\times dep_{lca_{i, j}})\\
\end{aligned}
\]
我们把后面括号拆开后发现前两项是相同的，最后一项可以直接虚树上 dp 求出来。
最后我们莫反一下，即可得到答案。
复杂度建虚树一个 \(\log\)，找倍数一个 \(\log\)，总共 \(O(n\log^2n)\)。
由于 haosen 不看图图，所以今天不放图了。
鉴于 haosen 求情，还是放张图吧。
