题解：P12003 在小小的奶龙山里面挖呀挖呀挖（加强版）
水星湖
·
·
题解
考虑到每个 a_i 大于 10^4 的质因子至多只有一个，可以树上莫队维护路径不同数个数 （SP10707），时间复杂度 \mathcal O(n\sqrt q)。枚举小于 10^4 的质数，对于每个质数就是要查 q 条路径上是否出现过这个质数，可以前缀和做到 \mathcal O(n+q)，总复杂度 \mathcal O(n\sqrt q + \pi(\sqrt V) (n+q))。
然后发现：
因为我没写代码，写了发现真卡不过（5.6s）。
怎么办呢？
这样复杂度就是 \mathcal O(n\sqrt q + \pi(\sqrt[3]V) (n+q))，而且还可以保证莫队修改常数比较小。
最优解第二。
让我们膜拜 Cai 老师/bx