問題一覧 > 通常問題

No.399 動的な領主

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 315 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 173
作問者 : koyumeishikoyumeishi / テスター : btkbtk
7 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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。