RT

很遗憾，您上传的题解 P2441题解 未能通过审核。原因是 数学公式未添加 LaTeX； 。

题解区也有暴力的题解，但都没讲为什么这题能暴力。

我看到这道题第一眼就是暴力处理。

然鹅 n <= 200000。

然后一句话如同久旱的甘雨让原本哒咩的暴力又行了起来：

- UPD：本题测试数据随机，可能是假题。

不懂暴力的人可能不懂这句话的意义。

举个栗子，你在 int 正整数范围内随机两个数 a，b。

利用高超的小学数学计算你会发现 gcd(a,b) > 1 的概率高达 31%。

(ps:三个数的概率是 47%，四个是 55%)

所以对于每次询问，暴力一次有 31% 机率做出。

两次 47%，三次 55%。

虽然最坏复杂度高达 O(n * k)，但随机下期望复杂度只有 O(k log n)

最后讲一下暴力。

对于操作一：暴力递归；

对于操作二：物理修改。

~~应该没有人暴力都不会打把。~~

AC代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector <int> e[N];
int n,k,fa[N],a[N];
void build(int x){//朴实建树 
	for(int i = 0;i < e[x].size();i++){
		int to = e[x][i];
		if(to == fa[x]) continue;
		fa[to] = x;
		build(to);
	}
}
int dfs(int x,int y){//朴实递归 
	if(x == 0) return -1;
	if(__gcd(a[x],a[y]) > 1) return x;
	return dfs(fa[x],y);
}
int main() {
	cin >> n >> k;
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	int x,y,o;
    for(int i = 1;i < n;i++){
    	scanf("%d%d",&x,&y);
    	e[x].push_back(y);
    	e[y].push_back(x);
	}
	build(1);
	for(int i = 1;i <= k;i++){
		scanf("%d",&o);
		if(o == 1){
			scanf("%d",&x);
			printf("%d\n",dfs(fa[x],x));
		} else if(o == 2) {
			scanf("%d%d",&x,&y);
			a[x] = y;
		}
	}
    return 0;
}

完结撒花