数据随机说明平均数高为 $\log(n)$，所以树高可得出约等于17。

如此鲜美的数据尽然可以直接暴力过，对于每个询问把询问节点一层一层往父跳，如满足要求直接返回答案。

#include <bits/stdc++.h>
using namespace std;

const int N=200009;
int a[N],fa[N];
int n,k,x,y,opt;
int gcd(int x,int y){
	if(y==0) return x;
	return gcd(y,x%y);
}
int solve(int x){
	int now=fa[x];
	while(now!=0){
		if(gcd(a[x],a[now])>1) return now;
		now=fa[now];
	}
	return -1;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		fa[y]=x;
	}
	while(k--)
	{
		scanf("%d",&opt);
		if(opt==1){
			scanf("%d",&x);
			printf("%d\n",solve(x));
		}
		else{
			scanf("%d%d",&x,&y);
			a[x]=y;
		}
	}
	return 0;
}