#P2441. 角色属性树

    ID: 4838 远端评测题 1000ms 512MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>数学树形结构枚举,暴力素数判断,质数,筛法

角色属性树

题目描述

绪萌同人社是一个有趣的组织,该组织结构是一个树形结构。有一个社长,直接下属一些副社长。每个副社长又直接下属一些部长……。

每个成员都有一个萌点的属性,萌点属性是由一些质数的萌元素乘积构成(例如,猫耳的值是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:本题测试数据随机,可能是假题。