rt

#include<bits/stdc++.h>
using namespace std;
namespace qwq{
	inline long long read(){
		long long n = 0;  
		long long f = 1;
		char c = getchar();
		while(c < '0' || c > '9'){
			if(c == '-') f = -1;
			c = getchar();
		}
		while(c >= '0' && c <= '9'){
			n = (n << 3) + (n << 1) + (c ^ 48);
			c = getchar();
		}
		return n * f;
	}
	inline void Write(long long x){
		if(x < 0){
			putchar('-');
			x = -x;
		}
		if(x > 9) Write(x / 10);
		putchar((x % 10) ^ 48);
		return;
	}
	inline void write(long long x, char c){
		Write(x);
		putchar(c);
	}
}
using namespace qwq;
long long n, q, a[100010], f[100010], ans[100010], ne[100010], ansne[100010];
vector<long long> ys[100010], v[100010], st[2000010];
long long find(long long x){
	if(f[x] != x) return f[x] = find(f[x]);
	return x;
}
void dfs(long long u, long long dep){
	ne[u] = dep;
	for(long long i = 0; i < ys[u].size(); i++){
		long long j = ys[u][i];
		if(!st[j].empty()){
			if(ansne[u] < ne[st[j].back()]){
				ansne[u] = ne[st[j].back()];
				ans[u] = st[j].back();
			}
		}
		st[j].push_back(u);
	}
	for(long long i = 0; i < v[u].size(); i++){
		dfs(v[u][i], dep+1);
	}
	for(long long i = 0; i < ys[u].size(); i++){
		long long j = ys[u][i];
		st[j].pop_back();
	}
	return ;
}
int main(){
	n = read(), q = read();
	for(long long i = 1; i <= n; i++){
		f[i] = i;
		a[i] = read();
		ans[i] = -1;
		for(long long j = 2; j * j <= a[i]; j++){
			if(a[i] % j == 0){
				while(a[i] % j == 0){
					a[i] /= j;
				}
				ys[i].push_back(j);
			}
		}
		if(a[i] != 0) ys[i].push_back(a[i]);
	}
	for(long long i = 1; i < n; i++){
		long long x, y;
		x = read(), y = read();
		v[x].push_back(y);
		f[find(y)] = x;
	}
	for(long long i = 1; i < n; i++){
		if(f[i] == i) dfs(i, 1);
	}
	for(long long i = 1; i <= q; i++){
		long long x;
		x = read();
		write(ans[x], '\n');
	}
	return 0;
}

题目描述

给你一棵有n个点的树，每个点有一个权值。

给出q次询问，每次询问一个点x，找出这个点的最近的祖先，使得这两个点的权值最大公约数不为1。