U230544 [sxyz NOIP 模拟赛] 4 树（tree）

[sxyz NOIP 模拟赛]4 树（tree）T4 ------------ 4s 512MB

由于前几场模拟赛的压轴题过于简单，花老师想要提高一下压轴题的难度，于是这道题便出现在了这个位置。 在本题中，你将会构造一棵很大很大的树。开始时你有一棵模板树，模板树包含 n个节点，节点标号为 1 − n。初始情况下，你的大树与模板树相同。 接下来你会进行 m 次操作，每次操作会指定一个模板树的子树 a，将其挂到大树中节点 b 的下方。并将新加入的子树节点按照其在模板树中的编号顺序标号。设模板树中这个子树节点的标号为 x1, x2, x3, ..., xk，其中 x1 < x2 < ... < xk，原来大树中有 L 个节点，则新加入的节点按照顺序标号为 L + 1, L + 2, ..., L + k 最后，为了确保你得到了这棵大树，你需要回答 q 次询问，每次询问给出两个大树中的节点 x, y，你需要求出 x 和 y 在大树中的距离是多少。本题中树边的权值为 1。

第一行三个整数 n, m, q 接下来 n − 1 行，每行两个整数，表示模板树中的一条边 接下来 m 行，每行两个整数 a, b，表示将模板树中 a 节点的子树挂到大树的 b 节点下，并重新标号 接下来 q 行，每行两个整数，表示一次询问

对于每次询问输出一行一个整数，表示答案

对于 30% 的数据，$n, m ≤ 10^3$ 对于另 40% 的数据，$b ≤ n$ 对于所有数据，$1 ≤ n, m, q ≤ 10^5, 1 ≤ a ≤ n, 1 ≤ b ≤ 当前大树中的节点数$