分数: 600 点
问题陈述
你有一棵树 N 顶点。顶点已编号 1 to N,以及 i第一条边连接顶点 A_i 和顶点 B_i.
让 d(x,y) 表示顶点之间的距离 x 和 y 在这棵树中。这里,顶点之间的距离 x 和 y 是从顶点开始的最短路径上的边数 x to 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第一个查询。
示例输入 1
5 3 4 4 5 2 5 1 5 3 4 1 1 2 5 3
示例输出 1
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.
示例输入 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