No.235 めぐるはめぐる (5)
問題文
ちゃろー、センパイ。
最新のVRを使ったゲーム「yukicoder王国の野望」をついに買いましたよ!
夏休みに、めぐる、yukicoder王国を何回か旅行する計画を立てているんですけど、今のうちにダンジョンにこもって旅費を稼ぐつもりなんです。
いくら稼げば良いのか、センパイ、計算してください!
yukicoder王国には $N$ 個の街と $N-1$ 個の道路があるんですね。
$k$ 個目の道路は街 $A_k$ と街 $B_k$ を結ぶ道路で、全ての街は道路をいくつか通って行き来できるようになっています。
めぐるの旅行はある街 $X$ からある街 $Y$ に道路で移動するんですけど、街 $X,Y$ も含めて、訪れる全ての街で一泊して観光するつもりなんですね。
今は街 $k$ で泊まる場合の宿泊費は $S_k$ なんですけど、この夏休みはyuki王様のパレードが予定されていて、宿泊費が変わっていくんですよね…。
街 $k$ にはインフレ係数 $C_k$ ってのが設定されているんですね。
王様が街 $X$ から街 $Y$ まで規模 $Z$ のパレードを行ったら、その後はずーっと、街 $X,Y$ も含めて、そのパレードの時に通った街の宿泊費が値上がりするんです。
それも、その街のインフレ係数と $Z$ を掛けた分だけ値上がりするんで、きついんですよね…。
現在から夏休みが終わるまでの、めぐるの旅行の予定とパレードの予定は合計で $Q$ 個あるんですよね。
めぐる、時系列順に予定 $1$, 予定 $2$, $\ldots$, 予定 $Q$ とすると、それぞれの予定は以下のどちらかの形式でメモをしているんです!
- $0\ X\ Y\ Z$:街 $X$ から街 $Y$ まで、規模 $Z$ の国王のパレードが開催されます
- $1\ X\ Y$:めぐるが街 $X$ から街 $Y$ まで旅行する予定です!
そういえば、yuki国王のパレードってとっても華やかで楽しいんですよ。
今度一緒に見に行きませんか?
う…、そうですよね…。
入力
$N$ $S_1$ $S_2$ $\cdots$ $S_N$ $C_1$ $C_2$ $\cdots$ $C_N$ $A_1$ $B_1$ $A_2$ $B_2$ $\quad \vdots$ $A_{N-1}$ $B_{N-1}$ $Q$ 予定 $1$ 予定 $2$ $\quad \vdots$ 予定 $Q$
ここで、予定 $k$ は
$0$ $X_k$ $Y_k$ $Z_k$
または
$1$ $X_k$ $Y_k$
のどちらかの形式ですよ!
$2 \leq N \leq 200000 = 2 \times 10^5$
$0 \leq S_k, C_k \leq 1000000006 = 10^9+6$
$1 \leq A_k, B_k \leq N, \;\; A_k \neq B_k$
$1 \leq Q \leq 200000 = 2 \times 10^5$
$1 \leq X_k, Y_k \leq N, \;\; X_k \neq Y_k$
$0 \leq Z_k \leq 1000000006 = 10^9+6$
出力
旅行の予定のたびに、予定通りにいった場合の、その旅行での必要な宿泊費を ${\rm mod}\ 1000000007$ で出力してくださいね!
サンプル
サンプル1
入力
8 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 6 1 1 5 1 3 2 7 2 1 2 4 8 4 6 1 1 7 1 8 5 0 6 3 100 1 5 3 0 7 5 10000 1 6 8
出力
10 20 1409 151121
最初の街 $1$~$8$ の宿泊費は $1,2,3,4,5,6,7,8$ ですね!
めぐるが最初 $1 \to 2 \to 7$ と旅行するときの宿泊費は $1+2+7$ で $10$ ですかね…。
次の旅行は $8 \to 4 \to 2 \to 1 \to 5$ だから、$8+4+2+1+5$ で $20$ ですね!
その後には王様のパレードが $6 \to 1 \to 3$ と行われるので、宿泊費は $801,2,603,4,5,306,7,8$ に変わりますかね…。
その次の旅行は $5 \to 1 \to 3$ だから、宿泊費は $5+801+603$ で $1409$ ですかね…。
その後には王様のパレードが $7 \to 2 \to 1 \to 5$ と行われるので、宿泊費は $80801,70002,603,4,40005,306,20007,8$ に変わりますかね…。変わりますよね……。
最後の旅行は $6 \to 1 \to 2 \to 4 \to 8$ だから、$306+80801+70002+4+8$ で $151121$ ですね…………。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。