题解满了，于是只能发在讨论版里。

---

前面推式子还是一样的，然后把 $d(u,v)$ 的贡献拆开，分给路径上的每条边。

设某条边断掉后两个子树的 $a$ 集合分别为 $S,T$。

问题变为对每条边求 $\sum\limits_iF(i)\big(\sum\limits_{i\mid a\in S} \varphi(a)\big) \big(\sum\limits_{i\mid b\in T}\varphi (b)\big)$

我们在dfn序上考虑这件事，那么容易得到根号log的莫队做法。

而子树的dfn区间有良好的性质，比如不存在相交。

于是我们可以分治，递归到一个区间时解决跨过中点的询问。

时间还是两只log，但代码非常好写。

提交记录

---

给个源码，以防有善良的管理员愿意把它加进题解里：

题解满了，于是只能发在讨论版里。

前面推式子还是一样的，然后把 $d(u,v)$ 的贡献拆开。

设某条边断掉后两个子树的 $a$ 集合分别为 $S,T$。

问题变为对每条边求 $\sum\limits_iF(i)\big(\sum\limits_{i\mid a\in S} \varphi(a)\big) \big(\sum\limits_{i\mid b\in T}\varphi (b)\big)$

我们在dfn序上考虑这件事，那么容易得到根号log的莫队做法。

而子树的dfn区间有良好的性质，比如不存在相交。

于是我们可以分治，递归到一个区间时解决跨过中点的询问。

时间还是两只log，但代码非常好写。

[提交记录](https://codeforces.com/problemset/submission/809/163203949)