P2441 角色属性树
题目描述
绪萌同人社是一个有趣的组织，该组织结构是一个树形结构。有一个社长，直接下属一些副社长。每个副社长又直接下属一些部长……。
每个成员都有一个萌点的属性，萌点属性是由一些质数的萌元素乘积构成（例如，猫耳的值是222，弱气的值是333，黄毛的值是555，病娇的值是777，双马尾的值是111111等等）
举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为2×2×3=122\times 2\times 3=122×2×3=12。
现在组员关心一个问题，希望知道离自己最近且有相同萌元素上司是谁，例如，属性值为2、4、6、452、4、6、452、4、6、45这样的属性值都算是和正妹有相同的属性。
然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。
输入格式
第一行，n,kn,kn,k表示成员数与询问的次数
第二行，nnn个数，分别是111到nnn号成员的属性值
接下来n−1n-1n−1行，xi,yix_i,y_ixi,yi表示xix_ixi是yiy_iyi的上司。
接下来来kkk行，有两种情况
1 ui1\ u_i1ui：询问离uiu_iui成员最近且有相同萌元素上司。
2 ui a2\ u_i\ a2uia：更改uiu_iui的属性值为aaa。
输出格式
对于每个111类型的询问，输出符合要求的编号。如果没有符合要求的编号，输出−1-1−1。
输入输出样例 #1
输入 #1
4 6 10 8 4 3 1 2 2 3 3 4 1 1 1 2 1 3 1 4 2 1 9 1 4输出 #1
-1 1 2 -1 1说明/提示
对于20%20\%20%的数据，没有修改的操作。
对于50%50\%50%的数据，n≤100n\le 100n≤100，修改次数<10<10<10。
对于100%100\%100%的数据，n≤200000n\le 200000n≤200000，k<100000k<100000k<100000，修改次数≤50,ai≤231−1\le 50,a_i\le 2^{31}-1≤50,ai≤231−1。
UPD：本题测试数据随机，可能是假题。
C++实现
#include<bits/stdc++.h>usingnamespacestd;inta[200001]={0};intfa[200001]={0};// father 数组intdfs(intx,inty){//搜索。if(x==0)return-1;if(__gcd(a[x],a[y])>1)returnx;//偷一下懒~直接使用gcd函数。returndfs(fa[x],y);}intmain(){intn,k;cin>>n>>k;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=n-1;i++){intx,y;cin>>x>>y;fa[y]=x;//建树}for(inti=1;i<=k;i++){intx,y;cin>>x;if(x==1){cin>>y;cout<<dfs(fa[y],y)<<endl;//搜索}else{cin>>x>>y;a[x]=y;}}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容