Score : $600$ points

问题描述

你被给定一棵包含 $N$ 个顶点的树。顶点按从 $1$ 到 $N$ 编号，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

令 $d(x,y)$ 表示在该树中顶点 $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))$。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:23:30