#PQJ30x5222. QOJ 30_5222
QOJ 30_5222
NOI2016 浙江省队选拔赛第二试 大森林 大森林 【问题描述】 小Y 家里有一个大森林,里面有 𝑛 棵树,编号从 1 到 𝑛 。一开始这些树都 只是树苗,只有一个节点,标号为 1 。这些树都有一个特殊的节点,我们称之为 生长节点,这些节点有生长出子节点的能力。 小Y 掌握了一种魔法,能让第 𝑙 棵树到第 𝑟 棵树的生长节点长出一个子节点。 同时她还能修改第 𝑙 棵树到第 𝑟 棵树的生长节点。 她告诉了你她使用魔法的记录,你能不能管理她家的森林,并且回答她的询 问呢? 【输入格式】 输入文件forest.in 第一行包含 2 个正整数 𝑛, 𝑚,共有 𝑛 棵树和 𝑚 个操作。 接下来 𝑚 行,每行包含若干非负整数表示一个操作,操作格式为: 1. 0 𝑙 𝑟 表示将第 𝑙 棵树到第 𝑟 棵树的生长节点下面长出一个子节点, 子节点的标号为上一个 0 号操作叶子标号加 1(例如,第一个 0 号 操作产生的子节点标号为 2), 𝑙 到 𝑟 之间的树长出的节点标号都相 同。保证 1 ≤𝑙≤𝑟≤𝑛 。 2. 1 𝑙 𝑟 𝑥 表示将第 𝑙 棵树到第 𝑟 棵树的生长节点改到标号为 𝑥 的节点。 对于 𝑖 (𝑙≤𝑖≤𝑟) 这棵树,如果标号 𝑥 的点不在其中,那么这个操 作对该树不产生影响。保证 1 ≤𝑙≤𝑟≤𝑛 , 𝑥 不超过当前所有树中 节点最大的标号。 3. 2 𝑥 𝑢 𝑣 询问第 𝑥 棵树中节点 𝑢 到节点 𝑣 点的距离,也就是在第 𝑥 棵 树中从节点 𝑢 和节点 𝑣 的最短路上边的数量。保证1 ≤𝑥≤𝑛,这棵 树中节点 𝑢 和节点 𝑣 存在。 【输出格式】 输出文件为forest.out。 输出包括若干行,按顺序对于每个小Y 的询问输出答案。 【样例输入1】 5 5 0 1 5 1 2 4 2
NOI2016 浙江省队选拔赛第二试 大森林 0 1 4 2 1 1 3 2 2 1 3 【样例输出1】 1 2 【样例输入输出2】 见选手目录下的forest/forest.in 与forest/forest.ans。 【数据规模和约定】 各测试点满足以下约定: 测试点 𝑛 𝑚 约定 1 ≤103 ≤103 无 2 ≤105 ≤2 × 105 保证每次 0 和 1 操作修改的是 1 到 𝑛 所有的树 3 4 保证每次 0 操作生长节点都是 这些树中编号最大的节点 5 6 无 7 8 9 10