给定一个有 n 个点的树和每个点的权值 a_i，q 次询问，每次询问查询 x 最近的祖先使其不与 x 互质。
1\le n\le 10^6，1\le q\le 10^6，1\le a_i\le 2\times 10^6。
教教我T5吧哥,给个思路就行
只要你教我T5我就帮你@人
@stringdp100005 我口胡了一个做法，不知道对不对qwq
首先线性筛预处理一下每个数字的最小质因子，这样就可以在 \log 复杂度内求出一个数的所有质因子。
然后用 DFS 从根开始扫，维护一个数组 \{f_i\}，其中 f_i 表示当前情况下值可以整除 i 的最近祖先。
DFS 的进入一个结点就备份一份，然后根据质因子找到 f_i 中存在的最小祖先，再更新一下 f，然后递归下去。离开的时候把备份复制回去即可。
然后这样预处理质因子 O(A+n\log A)，DFS O(n\log A)，常数应该不大可以过 10^6 吧
看到了麻烦回一下谢谢qwq
应该也挺好写的，没啥细节。。。
%%%tql
怎麽只有哦我現在在看小豬佩奇？
1 个赞
上大班了吗孩子
我还看熊出没和喜洋洋呢
呃,我一直觉得你非常年幼,因为头像感人
怎麽只有哦我現在在看豬豬俠？
好吧我摊牌,我在看这个
1 个赞
试图获得AK之力
我是真的在看小豬佩奇
1 个赞
省流：心有错论坛管理员试图将求助帖变为水贴。
1 个赞
嗚嗚嗚，巨佬別罵了。
1 个赞
%%%tql