#P2441. 角色属性树
角色属性树
题目描述
绪萌同人社是一个有趣的组织,该组织结构是一个树形结构。有一个社长,直接下属一些副社长。每个副社长又直接下属一些部长……。
每个成员都有一个萌点的属性,萌点属性是由一些质数的萌元素乘积构成(例如,猫耳的值是2,弱气的值是3,黄毛的值是5,病娇的值是7,双马尾的值是11等等)
举个例子,正妹是双份的猫耳,而且有一份弱气,她的属性值为2*2*3=12。
现在组员关心一个问题,希望知道离自己最近且有相同萌元素上司是谁,例如,属性值为2、4、6、45这样的属性值都算是和正妹有相同的属性。
然而,组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。
输入格式
第一行,n,k 表示成员数与询问的次数
第二行,n个数,分别是1~n号成员的属性值
接下来n-1行,x_i,y_i 表示x_i是y_i的上司。
接下来来k行,有两种情况
1 u_i 询问离u_i成员最近且有相同萌元素上司。
2 u_i a 更改u_i的属性值为a
输出格式
对于每个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
2
-1
1
提示
对于20%的数据,没有修改的操作。
对于50%的数据,n<=100,修改次数<10
对于100%的数据,n<=200000,k<100000 ,修改次数<=50,a_i<=2^31-1
UPD:本题测试数据随机,可能是假题。