#HNOI2016C. 树

    ID: 334 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>树结构最近公共祖先数据结构树套树2016各省省选湖南LCA主席树

题目描述

小A想做一棵很大的树,但是他手上的材料有限,只好用点小技巧了。开始,小A只有一棵结点数为 NN 的树,结点的编号为 1,2,...,N1,2,...,N,其中结点 11 为根;我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下:

  1. 将模板树复制为初始的大树。
  2. 以下(2.1)(2.2)(2.3)步循环执行 MM

(2.1)选择两个数字 a,ba,b,其中 1aN,1b当前大树的结点数1 \leq a \leq N, 1 \leq b \leq \text{当前大树的结点数}

(2.2)将模板树中以结点 aa 为根的子树复制一遍,挂到大树中结点 bb 的下方(也就是说,模板树中的结点 aa 为根的子树复制到大树中后,将成为大树中结点 bb 的子树)。

(2.3)将新加入大树的结点按照在模板树中编号的顺序重新编号。例如,假设在进行2.2步之前大树有 LL 个结点,模板树中以 aa 为根的子树共有 CC 个结点,那么新加入模板树的 CC 个结点在大树中的编号将是 L+1,L+2,...,L+CL+1,L+2,...,L+C ;大树中这C个结点编号的大小顺序和模板树中对应的 CC 个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图:

根据第(1)步,初始的大树与模板树是相同的。

在(2.1)步,假设选择了 a=4,b=3a=4, b=3。运行(2.2)和(2.3)后,得到新的大树如下图所示

现在他想问你,树中一些结点对的距离是多少。

输入格式

第一行三个整数:N,M,QN,M,Q,以空格隔开,NN 表示模板树结点数,MM 表示第(2)中的循环操作的次数,QQ 表示询问数量。

接下来 N1N-1 行,每行两个整数 fr,tofr,to,表示模板树中的一条树边。

再接下来MM行,每行两个整数x,tox,to,表示将模板树中 xx 为根的子树复制到大树中成为结点 toto 的子树的一次操作。

再接下来 QQ 行,每行两个整数 fr,tofr,to,表示询问大树中结点 frfrtoto 之间的距离是多少。

N,M,Q100000N,M,Q \leq 100000

输出格式

输出 QQ 行,每行一个整数,第 ii 行是第 ii 个询问的答案。

5 2 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3
6
3
3

提示

经过两次操作后,大树变成了下图所示的形状:

结点6到9之间经过了6条边,所以距离为6;类似地,结点1到8之间经过了3条边;结点5到3之间也经过了3条边。