题目描述

给定一个包含 $N$ 个顶点的树。顶点从 $1$ 到 $N$ 编号，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

设 $d(x,y)$ 表示树中顶点 $x$ 和 $y$ 之间的距离。这里，顶点 $x$ 和 $y$ 之间的距离是从顶点 $x$ 到顶点 $y$ 的最短路径上的边数。

按顺序回答 $Q$ 个查询。第 $i$ 个查询如下：

• 给定整数 $L_i$ 和 $R_i$。计算 $\\displaystyle\\sum_{j = 1}^{N} \\min(d(j, L_i), d(j, R_i))$。

约束条件

• $1 \\leq N, Q \\leq 2 \\times 10^5$
• $1 \\leq A_i, B_i, L_i, R_i \\leq N$
• 给定的图形是一棵树。
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出：

$N$ $A_1$ $B_1$ $\\vdots$ $A_{N-1}$ $B_{N-1}$ $Q$ $L_1$ $R_1$ $\\vdots$ $L_Q$ $R_Q$

输出

输出答案。

示例输入 1

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

示例输出 1

4
6
3

我们来解释一下第一个查询。
由于 $d(1, 4) = 2$，$d(1, 1) = 0$，所以有 $\\min(d(1, 4), d(1, 1)) = 0$。
由于 $d(2, 4) = 2$，$d(2, 1) = 2$，所以有 $\\min(d(2, 4), d(2, 1)) = 2$。
由于 $d(3, 4) = 1$，$d(3, 1) = 3$，所以有 $\\min(d(3, 4), d(3, 1)) = 1$。
由于 $d(4, 4) = 0$，$d(4, 1) = 2$，所以有 $\\min(d(4, 4), d(4, 1)) = 0$。
由于 $d(5, 4) = 1$，$d(5, 1) = 1$，所以有 $\\min(d(5, 4), d(5, 1)) = 1$。
因此，$0 + 2 + 1 + 0 + 1 = 4$，所以应该输出 $4$。

示例输入 2

8
4 2
4 1
5 6
6 1
7 6
8 1
3 7
7
8 4
4 4
7 2
4 4
5 3
4 4
6 1

示例输出 2

14
16
10
16
14
16
8