P3348 [ZJOI2016]大森林

    • 335通过
    • 703提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2016 浙江 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小Y家里有一个大森林,里面有n棵树,编号从1到n。一开始这些树都只是树苗,只有一个节点,标号为1。这些树都有一个特殊的节点,我们称之为生长节点,这些节点有生长出子节点的能力。

    小Y掌握了一种魔法,能让第l棵树到第r棵树的生长节点长出一个子节点。同时她还能修改第l棵树到第r棵树的生长节点。她告诉了你她使用魔法的记录,你能不能管理她家的森林,并且回答她的询问呢?

    输入输出格式

    输入格式:

    第一行包含 2 个正整数 n,m,共有 n 棵树和 m 个操作。

    接下来 m 行,每行包含若干非负整数表示一个操作,操作格式为:

    0 l r 表示将第 l 棵树到第 r 棵树的生长节点下面长出一个子节点,子节点的标号为上一个 0 号操作叶子标号加 1(例如,第一个 0 号操作产生的子节点标号为 2), l 到 r 之间的树长出的节点标号都相同。保证 1<=l<=r<=n 。

    1 l r x 表示将第 l 棵树到第 r 棵树的生长节点改到标号为 x 的节点。对于 i (l<=i<=r)这棵树,如果标号 x的点不在其中,那么这个操作对该树不产生影响。保证 1<=l<=r<=n , x 不超过当前所有树中节点最大的标号。

    2 x u v 询问第 x 棵树中节点 u 到节点 v 点的距离,也就是在第 x 棵树中从节点 u 和节点 v 的最短路上边的数量。保证1<=x<=n,这棵树中节点 u 和节点 v 存在。N<=10^5,M<=2*10^5

    输出格式:

    输出包括若干行,按顺序对于每个小Y的询问输出答案

    输入输出样例

    输入样例#1: 复制
    5 5
    0 1 5
    1 2 4 2
    0 1 4
    2 1 1 3
    2 2 1 3
    输出样例#1: 复制
    1
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。