最小距离之和

题目描述

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

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

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