当前没有测试数据。

Ex - 最小长度和

分数：600分

题目描述

给定一棵有$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$

输出

输出$Q$行。第$i$行应该包含第$i$个查询的答案。

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

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$。

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

14
16
10
16
14
16
8