@[lsj2009](/user/468657) 倍增 + `NTT` 维护前缀积。
by Usada_Pekora @ 2022-10-16 11:33:58
@[Zyingyzzz](/user/434929) 谢谢
by lsj2009 @ 2022-10-16 11:37:00
@[lsj2009](/user/468657) 这个做法依赖于值域（即乘积很大的时候复杂度会很烂）。
by Usada_Pekora @ 2022-10-16 11:42:20
@[Zyingyzzz](/user/434929) 所以这题还是没法做/kk
by lsj2009 @ 2022-10-16 11:50:03
@[lsj2009](/user/468657) 我好像想到一个。
对于所有质因子我们建一个树，然后每个数都插入到它可能的质因子里（这些可能的质因子总数也就十几二十几个）。
然后这个问题就变成了：遍历一个点的点权的所有质因子，然后查询这些质因子对应的导出子树里（若一个点 $i$ 的点权 $a_i$ 有这个质因子，那么它就在对应的导出子树里），这个点有没有一个父亲。
接下来开始做这个题目。
我们预处理原树的倍增数组 `fa[i][j]` 和树链剖分。
按照 dfs 序插入，对于点 $i$，具体地，有这样一个插入流程：
分解 $a_i$ 的质因数。
对于每个质因数对应的导出子树，我们考虑倍增一个点 $j$，满足这个点 $j$ 是 $i$ 的祖先，$j$ 在这个导出子树里，且 $j$ 是满足上面两个条件的深度最大点。
倍增点 $j$ 可以考虑利用树链剖分进行，复杂度 $O(\log^2n)$。
然后在这个导出子树里把 $i$ 接到 $j$ 上。
总预处理复杂度 $O(n(\sqrt {a_i}+\log^2n))$。
by Usada_Pekora @ 2022-10-16 12:29:17
哦，后面这个 $\log^2n$ 还要乘每个数不同质因子的个数。
by Usada_Pekora @ 2022-10-16 12:31:15
树链剖分和建导出子树需要利用动态开点缩减空间。常数超级大。
by Usada_Pekora @ 2022-10-16 12:32:38
感觉通过某种神秘离线做法应该可以优化。
by Usada_Pekora @ 2022-10-16 12:36:26
这个 $\log^2n$ 应该是 $\log^3n$。
by Usada_Pekora @ 2022-10-16 16:12:24