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了，可以的话，请您参考添加页面，与大家一起分享你的题解！