P2441 角色属性树

    • 55通过
    • 302提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 数论,数学 枚举,暴力 树形结构 素数判断,质数,筛法 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    每个成员都有一个萌点的属性,萌点属性是由一些质数的萌元素乘积构成(例如,猫耳的值是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。

    输入输出样例

    输入样例#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%的数据,没有修改的操作。

    对于50%的数据,n<=100,修改次数<10

    对于100%的数据,n<=200000,k<100000 ,修改次数<=50,a_i<=2^31-1

    528

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。