当前位置：首页 > news >正文

打卡信奥刷题（2604）用C++实现信奥题 P2441 角色属性树

news 2026/5/11 20:35:54

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;}