NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem68--树 [tree]

68: 树 [tree]

Time Limit: 2000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

小 A 想做一棵很大的树,但是他手上的材料有限,只好用点小技巧了。

开始,小 A 只有一棵结点数为 N 的树,结点的编号为 1,2,…,N,其中结点 1 为根;我们称这颗树为模板树。小 A 决定通过这棵模板树来构建一颗大树。构建过程如下:

(1)将模板树复制为初始的大树。

(2)以下(2.1)(2.2)(2.3)步循环执行 M 次

(2.1)选择两个数字 a,b,其中 1≤a≤N,1≤b≤当前大树的结点数。

(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)后,得到新的大树如下图所示:

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

Input

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

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

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

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

Output

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

Sample Input Copy

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

Sample Output Copy

6
3
3

HINT

【样例解释】

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

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

【数据范围】

对于 30%的数据,N,M<=500;

对于 60%的数据,N<=3000;

对于 100%的数据,N,M,Q<=100000。

Source/Category