← 返回题目列表

Codeforces · 1843/D

D. 苹果树

中文机器翻译题面 查看原题

Timofey 的花园里长着一棵苹果树;它是一棵由 $$$n$$$ 个顶点组成的有根树,根位于顶点 $$$1$$$(顶点编号从 $$$1$$$ 到 $$$n$$$)。树是一个没有循环和多条边的连通图。

这棵树非常不寻常——它的根部向上生长。不过,对于程序员的树来说,这是很正常的。

苹果树还很年轻,所以上面只会长两个苹果。苹果会在某些顶点生长(这些顶点可能是相同的)。苹果长大后,蒂莫菲开始摇晃苹果树,直到苹果掉落。每次蒂莫菲摇动苹果树时,每个苹果都会发生以下情况:

让苹果现在位于顶点$$$u$$$。

- 如果顶点 $$$u$$$ 有一个子顶点,则苹果会移动到该顶点(如果有多个这样的顶点,则苹果可以移动到其中任何一个)。
- 否则,苹果会从树上掉下来。

可以证明,在有限的时间后,两个苹果都会从树上掉下来。

Timofey 有 $$$q$$$ 假设,其中苹果的顶点可以生长。他假设苹果可以在顶点 $$$x$$$ 和 $$$y$$$ 中生长,并且想知道苹果可以从树上掉下来的顶点对 ($$$a$$$, $$$b$$$) 的数量,其中 $$$a$$$ - 顶点 $$$x$$$ 中的苹果将从中掉落的顶点,$$$b$$$ - 从顶点中掉落苹果的顶点顶点$$$y$$$将会掉落。帮助他做到这一点。

输入

第一行包含整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 树中的顶点数。

然后有 $$$n - 1$$$ 行描述树。 $$$i$$$ 行有两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — 树中的边。

下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — Timofey 假设的数量。

接下来的 $$$q$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) - 对于假设 $$$i$$$,苹果将在其上生长的假定顶点。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$。同样,保证$$$q$$$之和不超过$$$2 \cdot 10^5$$$。

输出

对于每个 Timofey 的假设,如果假设在单独的行上为真,则输出苹果可以从树上掉落的有序顶点对的数量。

示例

输入 #1

2
5
1 2
3 4
5 3
3 2
4
3 4
5 1
4 4
1 3
3
1 2
1 3
3
1 1
2 3
3 1

输出 #1

2
2
1
4
4
1
2

输入 #2

2
5
5 1
1 2
2 3
4 3
2
5 5
5 1
5
3 2
5 3
2 1
4 2
3
4 3
2 1
4 2

输出 #2

1
2
1
4
2

注意

在第一个示例中:

- 对于第一个假设,苹果可以从树上掉下来的两个可能的顶点对:$$$(4, 4), (5, 4)$$$。
- 对于第二个假设,也有两对:$$$(5, 4), (5, 5)$$$。
- 对于第三个假设,只有一对:$$$(4, 4)$$$。
- 对于第四个假设,有 $$$4$$$ 对:$$$(4, 4), (4, 5), (5, 4), (5, 5)$$$。

第一个示例中的树。

对于第二个示例,苹果可以从 $$$4$$$ 可能的顶点对掉落:$$$(2, 3), (2, 2), (3, 2), (3, 3)$$$。对于第二个假设,只有一对可能的:$$$(2, 3)$$$。对于第三个假设,有两对:$$$(3, 2), (3, 3)$$$。