AT_abc298_h.[ABC298Ex] Sum of Min of Length

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

此外，树上顶点 $x$ 和顶点 $y$ 之间的距离记作 $d(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$ 个查询的答案。

数据范围

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i, B_i, L_i, R_i \leq N$
• 给定的图为树
• 所有输入均为整数

样例解释 1

以第 $1$ 个查询为例。$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$。

由 ChatGPT 4.1 翻译