No.386 貪欲な領主 のアレンジバージョンです。

問題文

とある国に $N$ 個の村があります。
村々は $N-1$ 本の街道で互いに結ばれており、自由に行き来することができます。

この国の領主は税収を増やすため、村々に関所を置き、ここを通る行商人に関税を課すことにしました。
行商人は村を通るたび、 $$ 関税が施行されてから今までにその村を通った行商人の数 + 1 $$ 単位のお金を納めなければなりません。
需要が高ければ価格も高くなる、経済の常ですよね。

関税が施行されて以降、 $Q$ 人の行商人がそれぞれ 村$A_i$ から 村$B_i$ へ、街道を通って最短経路で移動したことがわかっています。
国が得ることになる関税の合計金額を出力してください。

ただし行商人は途中立ち寄る村の関所にだけではなく、村$A_i$、村$B_i$の関所にも関税を納めなければなりません。

入力

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$Q$
$A_1$ $B_1$
$\vdots$
$A_Q$ $B_Q$

入力は全て整数で与えられます。
$1$行目には村の数$N$、続く $N-1$ 行に街道の結ぶ村の情報が与えられます。
$i$ 番目の街道は 村$u_i$ と 村$v_i$ を結びます。
$N+1$ 行目には行商人の数$Q$が与えられます。
以降 $Q$ 行に、$i$番目の行商人の出発地点の村$A_i$ と 最終到達地点の村$B_i$が与えられます。

また、入力は以下の制約を満たします。
$2 \leq N \leq 10^5$
$1 \leq u_i, v_i \leq N$
$u_i \neq v_i$
$1 \leq Q \leq 10^5$
$1 \leq A_i, B_i \leq N$
$A_i \neq B_i$

出力

関税の合計金額を1行に出力してください。 答えは32ビット整数に収まらないことがあるので注意して下さい。

サンプル

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

15

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

75