## 题目
$\text{给定一棵带有权值的树，有少量权值修改操作，每次询问求一个点最近的有相同质因子的祖先。}$
## 想法
最近的祖先？是$LCA$吗？
题目可以转化为：树上最近和自己权值的$gcd$大于一的祖先
~~等于没说~~
为什么呢？因为~~楼上有人讲了~~。
那现在考虑如何倍增求这个东西。
和$LCA$一样，从当前这个点出发，往上以$2$的次幂递减的步长往上跳，能跳则跳。那怎样才算能跳呢？
显然，对于每个点只维护自己的权值是远远不够的，这启发我们还要维护一些关于区间的信息，即倍增时的那些$2$次幂的区间。
那现在再来考虑需要什么：
还是那个问题：怎样才算能跳。能跳的前提是跳了不会错过答案，即跳的区间里没有答案。这个区间里的数比深度更小的数更近，故这些数必须满足的条件是：这里的数都和询问的数没有相同质因子！！！
举个栗子：
5 -> 9 -> 8 -> 53 -> 16
17本想跳到$2^2$处，但这中间有8和16有相同质因子，所以不能跳，再考虑$2^1$处，同样有8，所以也不能跳，最后考虑$2^0$，欸，没有了，可以跳了！于是跳到了53。因为这是跳到了答案的下一个，所以还得再跳一次就可以了。
现在需要维护什么就维护什么就好了。但怎么维护嘞？很明显，如果一个区间中任何一个都和询问的数没有相同质因子，那就算把它们都乘起来也没有，反之也成立。
现在只需要维护区间乘积了！！！有两种方法：
1.倍增时另计$g[i][j]=g[i][j-1]*g[f[f[i][j-1]][0]][j-1]$，时间空间复杂度均为$O(nlogn)$
2.计算每个点到根的乘积，~~可以叫树上前缀积吧~~？查询一个区间时，用两端的前缀积作商即可，时间空间复杂度均为$O(n)$
显然后者更优。~~废话~~。但是有一个问题，就是单纯的乘积一定会算术上溢，怎么办呢？
> 孩子不想写高精度，怎么办呢？
> 不想写高精度，一定是用c++的，转python就好了。
算一算，$k$次询问，每次倍增时有$logn$的尝试和每次尝试的$gcd$有$logsum=log(2^{32}*n)=32*logn=logn$，还有$50$次暴力修改，所以理论复杂度为$O((klog^2n+50n)*$~~巨大常数~~$)$。
## 声明
理论复杂度是可以接受的，但也许是常数太大了吧，连我自己都[没过](https://www.luogu.com.cn/record/29832083)。虽然数据是随机的，但我$\color{lightgreen}{AC}$7个点，$\color{blue}{TLE}$3个点。如果哪位大佬能救这位蒟蒻，请在评论区指点迷津，谢谢！！！
## 代码
码风很奇怪，不要介意。
```python
def gcd(x,y):
if y==0:
return x
return gcd(y,x%y)
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,1)
b=[]
c=[] #children
d=[] #depth
f=[] #father
lg=[0] #log(2,i)
root=0 #root
def DFS(u):
for v in c[u]:
b[v]=a[v]*b[u]
d[v]=d[u]+1
DFS(v)
def ask(x):
y=x
for i in range(lg[d[x]]-1,-1,-1):
if gcd(b[y]//a[y]//b[f[f[y][i]][0]],a[x])==1:
y=f[y][i]
if f[y][0]==0:
return -1
return f[y][0]
for i in range(1,n+3):
b.append(1)
d.append(0)
c.append(list())
f.append(list())
lg.append(lg[i//2]+1)
for i in range(1,n):
x,y=map(int,input().split())
c[x].append(y)
f[y].append(x)
for i in range(1,lg[n]+2):
for j in range(0,n+2):
f[j].append(0)
for i in range(1,lg[n]):
for j in range(1,n+1):
f[j][i]=f[f[j][i-1]][i-1]
for i in range(1,n+1):
if f[i][0]==0:
root=i
break
b[root]=a[root]
DFS(root)
for i in range(k):
q=list(map(int,input().split()))
if q[0]==1:
print(ask(q[1]))
else:
a[q[1]]=q[2]
b[root]=a[root]
DFS(root)
DFS(root)
```