一棵树，点权 \(a_i(a_i\le n)\)，无边权，求
\[\sum_{i\ne j}\varphi(a_ia_j)\text{dis}(i,j) \]首先，你没有任何手段求 \(10^{10}\) 级别的一堆离散的 \(\varphi\)。于是
\[\varphi(xy)=\frac{\varphi(x)\varphi(y)\gcd(x,y)}{\varphi(\gcd(x,y))} \]然后一通莫反，枚举 \(\gcd\)
\[\sum_{d=1}^n \sum_{x=1}^n \sum_{y=1}^n [\gcd(x,y)=d]\frac{\varphi(x)\varphi(y)d}{\varphi(d)}\sum_{a_i=x,a_j=y}\text{dis}(i,j) \]\[\sum_{T=1}^n\left(\sum_{d|T}\mu\left(\frac Td\right)\frac d{\varphi(d)}\right)\left(\sum_{x=1}^{n/T} \sum_{y=1}^{n/T} \varphi(xT)\varphi(yT) \sum_{a_i=x_T,a_j=y_T}\text{dis}(i,j)\right) \]前者暴力求，后者就是
\[\sum_{T=1}^n \sum_{i\ne j}[T|a_i,T|a_j] \varphi(a_i)\varphi(a_j)\text{dis}(i,j) \]可以点分。或者对于每个 \(T\) 把 \(a\) 为 \(T\) 的倍数的点暴力揪出来建虚树，然后
\[\sum_{i=1}^k \varphi(a_i) \sum_{j=1,j\ne i}^k \varphi(a_j)\text{dis}(i,j) \]可以换根dp。保证 \(a\) 为排列的话总复杂度 \(O(n\ln n)\)。否则可以卡成 \(\Theta(n\max_{x=1}^n \sigma(x))\)。
标签：frac,gcd,题解,sum,varphi,text,CF809E,dis From： https://www.cnblogs.com/vanspace/p/cf809e.html