hack，数据在附件

本题所有有代码的题解，经过本地和洛谷的测试，均无法通过本题。

下面给出我的做法：

由于修改次数很少，故一开始和每次修改之后重算所有点的答案。

首先将所有点权使用 $\text{Pollard-Rho}$ 质因数分解，对于每个质因数分开处理。每个数不同质因数的个数之和有上界 $O(n \omega(n))$。

对于每个质因数，将所有点按照其入栈序排序，并用类似虚树的方法找到离每个点最近的祖先。按入栈序排序可以使用桶排实现。注意 $\text{LCA}$ 需要 $O(1)$ 查询。

设点权的值域为 $w$，修改操作的次数为 $t$，则时间复杂度为 $O((n+t)w^{\frac{1}{4}}+tn\omega(w))$，经过卡常可以通过此题。

请求撤下本题目前的所有题解，添加 $\text{hack}$ 数据，适当开大本题时限，并调整本题的难度评分。 感谢管理员 qwq