問題一覧 > 通常問題

No.235 めぐるはめぐる (5)

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 84
作問者 : LayCurseLayCurse
4 ProblemId : 640 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:32

問題文

ちゃろー、センパイ。
最新のVRを使ったゲーム「yukicoder王国の野望」をついに買いましたよ!
夏休みに、めぐる、yukicoder王国を何回か旅行する計画を立てているんですけど、今のうちにダンジョンにこもって旅費を稼ぐつもりなんです。
いくら稼げば良いのか、センパイ、計算してください!

yukicoder王国には N 個の街と N1 個の道路があるんですね。
k 個目の道路は街 Ak と街 Bk を結ぶ道路で、全ての街は道路をいくつか通って行き来できるようになっています。
めぐるの旅行はある街 X からある街 Y に道路で移動するんですけど、街 X,Y も含めて、訪れる全ての街で一泊して観光するつもりなんですね。
今は街 k で泊まる場合の宿泊費は Sk なんですけど、この夏休みはyuki王様のパレードが予定されていて、宿泊費が変わっていくんですよね…。

k にはインフレ係数 Ck ってのが設定されているんですね。
王様が街 X から街 Y まで規模 Z のパレードを行ったら、その後はずーっと、街 X,Y も含めて、そのパレードの時に通った街の宿泊費が値上がりするんです。
それも、その街のインフレ係数と Z を掛けた分だけ値上がりするんで、きついんですよね…。

現在から夏休みが終わるまでの、めぐるの旅行の予定とパレードの予定は合計で Q 個あるんですよね。
めぐる、時系列順に予定 1, 予定 2, , 予定 Q とすると、それぞれの予定は以下のどちらかの形式でメモをしているんです!

  • 0 X Y Z:街 X から街 Y まで、規模 Z の国王のパレードが開催されます
  • 1 X Y:めぐるが街 X から街 Y まで旅行する予定です!

そういえば、yuki国王のパレードってとっても華やかで楽しいんですよ。
今度一緒に見に行きませんか?
う…、そうですよね…。

入力

N
S1 S2  SN
C1 C2  CN
A1 B1
A2 B2

AN1 BN1
Q
予定 1
予定 2

予定 Q

ここで、予定 k

0 Xk Yk Zk

または

1 Xk Yk

のどちらかの形式ですよ!

2N200000=2×105
0Sk,Ck1000000006=109+6
1Ak,BkN,AkBk
1Q200000=2×105
1Xk,YkN,XkYk
0Zk1000000006=109+6

出力

旅行の予定のたびに、予定通りにいった場合の、その旅行での必要な宿泊費を 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

最初の街 18 の宿泊費は 1,2,3,4,5,6,7,8 ですね!
めぐるが最初 127 と旅行するときの宿泊費は 1+2+710 ですかね…。
次の旅行は 84215 だから、8+4+2+1+520 ですね!
その後には王様のパレードが 613 と行われるので、宿泊費は 801,2,603,4,5,306,7,8 に変わりますかね…。
その次の旅行は 513 だから、宿泊費は 5+801+6031409 ですかね…。
その後には王様のパレードが 7215 と行われるので、宿泊費は 80801,70002,603,4,40005,306,20007,8 に変わりますかね…。変わりますよね……。
最後の旅行は 61248 だから、306+80801+70002+4+8151121 ですね…………。

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