Skip to content

1001: Angel Beats! 2nd Beats!

题目

题目描述

向着这污秽不堪丑陋不堪的世界中所相遇的奇迹致谢。——岩泽雅美《Crow Song》

天使立华奏攻入了死后世界战线(SSS)的地下工会Guild,这是万分危急的时候。仲村由理指挥工会成员有条不紊地进行撤退工作。工会成员在Guild最深层工厂安放炸药需要很长的准备时间,需要有人来拖延立华奏的前进速度。但是他们并不清楚立华奏的具体位置,因此他们需要设立许多个防御点。

Guild的结构可以看成一棵有$n$个节点的有根树,有时由理会得到立华奏的大概位置,可能在某两棵子树的任意一棵中,她就会找到Guild树(不一定要在两棵子树内)上的一个点,使得该点到两棵子树中所有点距离(本题中的距离定义为两点之间最短路径的边数})之和最小,即这两棵子树的重心(如果两棵子树有重合部分,那么取它们并集求重心)。

由于Guild的过于庞大和错综复杂,有时也可能会有新的节点被发现。具体而言,我们会新建一个点,编号为已有的点数$+1$,通过一条边和原本的树相连。

我们会给定初始时Guild的结构($1$号节点为根),会有$q$个操作。操作分为新加入一个节点,和向你查询点$x$子树和点$y$子树的重心两种。你需要对于查询操作输出答案。重心可能会有很多个,你只需要输出距离和即可(如果两棵子树有重合部分,那么输出重心到两棵子树并集的距离和)。

输入格式

文件第一行有两个正整数$n$和$q$。

接下来$n-1$行,第$i$行表示节点$i$的父亲节点。

接下来$q$行,每行开头是$1$或$2$。

如果是$1$,其后会有两个正整数$x$和$y$,表示查询子树$x$和子树$y$的重心,你仅需要输出这个点到两棵子树中所有点距离之和(具体见题目描述)。

如果是$2$,其后会有一个正整数$x$,表示在点$x$的下面接一个儿子节点,编号为当前点数$+1$。

保证输入的$x$和$y$都能表示当前已经存在的点。

输出格式

对于每一个$1$操作,输出你求得的距离。

样例输入

9 3 1 2 3 3 7 2 7 1 1 3 7 1 3 2 1 7 9

样例输出

10 10 5

数据范围

$1\leq n,q\leq 3\times 10^4$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!