P3248 [HNOI2016] 树
题目描述
小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为 $N$ 的树，结点的编号为 $1,2,...,N$，其中结点 $1$ 为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：
1. 将模板树复制为初始的大树。
2. 以下(2.1)(2.2)(2.3)步循环执行 $M$ 次
（2.1）选择两个数字 $a,b$，其中 $1 \leq a \leq N, 1 \leq b \leq \text{当前大树的结点数}$。
（2.2）将模板树中以结点 $a$ 为根的子树复制一遍，挂到大树中结点 $b$ 的下方(也就是说，模板树中的结点 $a$ 为根的子树复制到大树中后，将成为大树中结点 $b$ 的子树)。
（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有 $L$ 个结点，模板树中以 $a$ 为根的子树共有 $C$ 个结点，那么新加入模板树的 $C$ 个结点在大树中的编号将是 $L+1,L+2,...,L+C$ ；大树中这C个结点编号的大小顺序和模板树中对应的 $C$ 个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：
根据第(1)步，初始的大树与模板树是相同的。
在(2.1)步，假设选择了 $a=4, b=3$。运行(2.2)和(2.3)后，得到新的大树如下图所示
现在他想问你，树中一些结点对的距离是多少。
输入格式
无
输出格式
无
说明/提示
经过两次操作后，大树变成了下图所示的形状：
结点6到9之间经过了6条边，所以距离为6；类似地，结点1到8之间经过了3条边；结点5到3之间也经过了3条边。