CF1843D.Apple Tree

Timofey has an apple tree growing in his garden; it is a rooted tree of $n$ vertices with the root in vertex $1$ (the vertices are numbered from $1$ to $n$). A tree is a connected graph without loops and multiple edges.

This tree is very unusual — it grows with its root upwards. However, it's quite normal for programmer's trees.

The apple tree is quite young, so only two apples will grow on it. Apples will grow in certain vertices (these vertices may be the same). After the apples grow, Timofey starts shaking the apple tree until the apples fall. Each time Timofey shakes the apple tree, the following happens to each of the apples:

Let the apple now be at vertex $u$.

• If a vertex $u$ has a child, the apple moves to it (if there are several such vertices, the apple can move to any of them).
• Otherwise, the apple falls from the tree.

It can be shown that after a finite time, both apples will fall from the tree.

Timofey has $q$ assumptions in which vertices apples can grow. He assumes that apples can grow in vertices $x$ and $y$, and wants to know the number of pairs of vertices ($a$, $b$) from which apples can fall from the tree, where $a$ — the vertex from which an apple from vertex $x$ will fall, $b$ — the vertex from which an apple from vertex $y$ will fall. Help him do this.

蒂莫菲的花园里长着一棵苹果树；这是一棵以顶点 $1$ 为根的、包含 $n$ 个顶点的有根树（顶点编号从 $1$ 到 $n$）。树是一种无环且无重边的连通图。

这棵树非常特别——它倒着生长，即根在上方。不过，对程序员而言，这种树却十分常见。

这棵苹果树尚且年幼，因此树上只会结出两个苹果。苹果将长在某些顶点上（这两个顶点可能相同）。苹果长成后，蒂莫菲便开始摇晃苹果树，直至苹果全部掉落。每次摇晃时，每个苹果将发生如下变化：

设当前苹果位于顶点 $u$。

• 若顶点 $u$ 存在子节点，则苹果会移动至其中一个子节点（若存在多个子节点，苹果可任选其一移动）；
• 否则，苹果将从树上掉落。

可以证明：经过有限次摇晃后，两个苹果最终都会从树上掉落。

蒂莫菲共有 $q$ 种关于苹果生长位置的假设。在每种假设中，他假设苹果分别长在顶点 $x$ 和 $y$ 上，并希望知道苹果最终可能掉落的顶点对 $(a, b)$ 的数量，其中 $a$ 表示从顶点 $x$ 出发的苹果最终掉落的顶点，$b$ 表示从顶点 $y$ 出发的苹果最终掉落的顶点。请帮助他解决这个问题。

The first line contains integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of vertices in the tree.

Then there are $n - 1$ lines describing the tree. In line $i$ there are two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) — edge in tree.

The next line contains a single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of Timofey's assumptions.

Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq n$) — the supposed vertices on which the apples will grow for the assumption $i$.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$. Similarly, It is guaranteed that the sum of $q$ does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each Timofey's assumption output the number of ordered pairs of vertices from which apples can fall from the tree if the assumption is true on a separate line.

对于蒂莫费伊的每一条假设，请在单独一行输出：若该假设成立，则苹果可能从树上掉落的顶点有序对的数量。

In the first example:

• For the first assumption, there are two possible pairs of vertices from which apples can fall from the tree: $(4, 4), (5, 4)$.
• For the second assumption there are also two pairs: $(5, 4), (5, 5)$.
• For the third assumption there is only one pair: $(4, 4)$.
• For the fourth assumption, there are $4$ pairs: $(4, 4), (4, 5), (5, 4), (5, 5)$.

Tree from the first example.

For the second example, there are $4$ of possible pairs of vertices from which apples can fall: $(2, 3), (2, 2), (3, 2), (3, 3)$. For the second assumption, there is only one possible pair: $(2, 3)$. For the third assumption, there are two pairs: $(3, 2), (3, 3)$.

在第一个例子中：

• 对于第一种假设，苹果可能从树上掉落的顶点对有两个：$(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)$。