配点 : $600$ 点

問題文

$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))$ の値を求めてください。

制約

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

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

4
6
3

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

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