题目描述

$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$ 番目のクエリに対する答えを出力せよ。

题目大意

给定一棵有 $n$ 个结点的树，共 $m$ 次询问，每次询问结点 $L,R$，求 $\begin{aligned}\sum_{i=1}^n\min\{d(i,L),d(i,R)\}\end{aligned}$，其中 $d(x,y)$ 表示 $x$ 结点到 $y$ 结点的距离。

translated by 月。

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

4
6
3

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

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$
• 与えられるグラフは木
• 入力はすべて整数

Sample Explanation 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$ を出力します。