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

問題文

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

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

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

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

入力

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

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

また、入力は以下の制約を満たします。
$2\le N\le {10}^5$
$1\le u_i,v_i\le N$
$u_i\ne v_i$
$1\le Q\le {10}^5$
$1\le A_i,B_i\le N$
$A_i\ne 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