自动搬运

查看原文

来自洛谷，原作者为

	Zilljy258 太沙雕了，，，

搬运于2025-08-24 21:37:44，当前版本为作者最后更新于2022-06-07 19:44:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暴力：编程界最热门的算法。

题目传送门

大体思路：

建一棵树，对于每次询问暴力搜索，对于每次更改进行实时的更改。

怎么暴力搜索？

其实“两个成员有相同的属性”说白了就是“两个成员的属性值的 $\gcd(a_x,a_y) > 1$”

所以只要顺着 $father$ 数组顺藤摸瓜，一个一个的枚举上司的属性值问题就解决了。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[200001]={0};
int fa[200001]={0};  // father 数组
int dfs(int x,int y){     //搜索。
	if(x == 0) return -1;
	if(__gcd(a[x],a[y]) > 1) return x;  //偷一下懒~直接使用gcd函数。
	return dfs(fa[x],y);
}
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		fa[y]=x;  //建树
	}
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x;
		if(x==1){
			cin>>y;
			cout<<dfs(fa[y],y)<<endl;  //搜索
		}
		else{
			cin>>x>>y;
			a[x]=y;
		}
	} 
	return 0;
} 

总结：

学好暴力很重要。

此题并不难，注意枚举和建树就好了。

后记：这是萌新第二次写题解，可能有不足之处，如果大家有要我补充的或改进的，一定要提出来！谢谢大家。