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 翻译