P4689 [Ynoi2016]这是我自己的发明

    • 149通过
    • 424提交
  • 题目提供者 noip 毒瘤
  • 评测方式 云端评测
  • 标签 构造 离散化 莫队 2016 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1500ms / 512MB

题解

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

    推荐的相关题目 显示

    题目背景

    一切伟大的世界历史事件与人物,可以说都会出现两次

    第一次是作为悲剧出现

    第二次,则是作为笑剧出现

    ——《路易.波拿马的雾月十八日》

    感动、

    痛苦、

    以及快乐、

    都只是遥不可及的宝石

    即便如此,人们啊,

    获得幸福吧!

    世界将在7月20日终结

    世界回归天空的日子

    万物被天空侵染的日子

    回归天空的日子

    世界必须回归

    世界的极限

    世界的尽头

    世界的终结

    你看…那就是极限…最尽头的天空

    如今,已无应该之事了如今,已无忘却之物了

    不需要的话语

    告别了永不相交的平行,我被吸进了…

    垂直下落的世界

    虽哭亦喜

    虽悲亦喜

    各种感情混在一起...

    比起其他所有,想必还是高兴占多吧

    她高兴地抱着我

    紧紧地抱着

    再也不会松开了...

    想永远这样...

    她的思绪,以比语言更快的速度,传达给了我

    有些东西,比语言更快

    她的思绪,以比语言更快的速度,传达给了我

    有些东西,比语音更准确

    世界上无论多么短暂的瞬间,都有意义

    有意义

    块临近终结了

    最后的瞬间

    啊啊...

    远方的警笛声

    黑色的天空

    月正笑

    地正润潮

    星正舞

    风正凉

    在我怀中,温暖的,

    橘希实香

    她在我的怀中...静静地合上了双眼

    然后我也...

    静静地合上了双眼

    题目描述

    您正在打galgame,然后突然家长进来了,于是您假装在写数据结构题:

    给一个树,n 个点,有点权,初始根是 1。

    m 个操作,每次操作:

    1.将树根换为 x。

    2.给出两个点 x,y,从 x 的子树中选每一个点,y 的子树中选每一个点,如果两个点点权相等,ans++,求 ans。

    输入输出格式

    输入格式:

    第一行两个数表示 n,m。

    第二行 n 个数,表示每个点的点权 a[i]​。

    之后 n − 1 行 , 每行两个数 x , y , 表示一条边

    之后 m 行,每行为 1 x 或者 2 x y。

    1 x,表示将根变成 x点。

    2 x y,表示查询 x 点的子树与 y 点的子树。

    输出格式:

    对于每个询问,输出一个数表示答案。

    输入输出样例

    输入样例#1: 复制
    5 5
    1 2 3 4 5
    1 2
    1 3
    3 4
    3 5
    2 4 5
    2 1 5
    2 3 5
    1 5
    2 4 5
    输出样例#1: 复制
    0
    1
    1
    1

    说明

    n <= 100000 , m <= 500000 , 1 <= a[i] <= 1000000000

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