102987: [Atcoder]ABC298 Ex - Sum of Min of Length

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$.

Let $d(x,y)$ denote the distance between vertex $x$ and $y$ in this tree. Here, the distance between vertex $x$ and $y$ is the number of edges on the shortest path from vertex $x$ to $y$.

Answer $Q$ queries in order. The $i$-th query is as follows.

• You are given integers $L_i$ and $R_i$. Find $\displaystyle\sum_{j = 1}^{N} \min(d(j, L_i), d(j, R_i))$.

Constraints

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i, B_i, L_i, R_i \leq N$
• The given graph is a tree.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$Q$
$L_1$ $R_1$
$\vdots$
$L_Q$ $R_Q$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

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

Sample Output 1

4
6
3

Let us explain the first query.
Since $d(1, 4) = 2$ and $d(1, 1) = 0$, we have $\min(d(1, 4), d(1, 1)) = 0$.
Since $d(2, 4) = 2$ and $d(2, 1) = 2$, we have $\min(d(2, 4), d(2, 1)) = 2$.
Since $d(3, 4) = 1$ and $d(3, 1) = 3$, we have $\min(d(3, 4), d(3, 1)) = 1$.
Since $d(4, 4) = 0$ and $d(4, 1) = 2$, we have $\min(d(4, 4), d(4, 1)) = 0$.
Since $d(5, 4) = 1$ and $d(5, 1) = 1$, we have $\min(d(5, 4), d(5, 1)) = 1$.
$0 + 2 + 1 + 0 + 1 = 4$, so you should print $4$.

Sample Input 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

Sample Output 2

14
16
10
16
14
16
8

问题描述

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

令$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))$。

约束

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