No.399 動的な領主

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 315 MB / 通常問題
タグ : / 解いたユーザー数 81
作問者 : koyumeishikoyumeishi / テスター : btkbtk
5 ProblemId : 1249 / 出題時の順位表
問題文最終更新日: 2016-07-16 01:58:20

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ビット整数に収まらないことがあるので注意して下さい。

サンプル

サンプル1
入力
6
1 2
2 3
2 4
1 5
5 6
3
1 2
3 4
4 6
出力
15

3人の行商人が順番に移動したと仮定すると(出力するのは合計なので実際に個々が払った額はどうでもいい)、
1人目は 村1 に 1単位、 村2 に 1単位 の関税を納めます。
2人目は 村3 に 1単位、 村2 に 2単位、 村4 に 1単位 の関税を納めます。 村2 はすでに行商人1 が通っているので、2単位の関税を納めなければなりません。
3人目は 村4 に 2単位、 村2 に 3単位、 村1 に 2単位、 村5 に 1単位、 村6 に 1単位 の関税を納めます。
合計すると 1+1+1+2+1+2+3+2+1+1 = 15 になります。

サンプル2
入力
5
1 2
2 3
3 4
4 5
5
1 5
1 5
1 5
1 5
1 5
出力
75

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。