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

输入 #1

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

输出 #1

4
6
3

输入输出样例 #2

输入 #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

说明/提示

数据范围

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