Time Limit: 2 sec / Memory Limit: 256 MB
問題文
岩井君はよく山に登る, 山登りのプロです(事実). 今日, 岩井くんは, 奇抜な形状をしていることで有名な窮理山への登山に挑戦します.
岩井君は窮理山の山頂まで登りたいです. また, 頂上で最高の眺めを楽しみ, できるだけ登山時に消耗する体力を減らすため, 岩井君はいつも山頂までたどり着くためのの最短ルートを使い登山をします. しかし窮理山ではよく土砂崩れが発生し, 道を通ることができなくなることがあります. さらにこの山は誰も管理していないので, 一度土砂崩れが起きるとその道を通ることは2度とできなくなります.
岩井君は山に登りに行く際, それまでに得られた土砂崩れの情報から, 登山コースを決めています. 山道の形と時系列順に並んだ土砂崩れの情報が与えられるので, それぞれの情報の後で利用できる最短ルートの距離を, コンピュータサイエンスの力で岩井君に教えてあげてください.
課題
N 頂点からなる根付き木と Q 個のクエリが与えられる. それぞれの頂点には 1 から N の整数の番号が付いており, 頂点 1 がこの木の根である. 頂点 i(≧2) は頂点 p_i(<i) を親に持ち, p_i と i を繋ぐ辺はコスト w_i を持つ.
最初,全ての辺を使用できる.それぞれのクエリは "辺 (x_i,p_{x_i}) を今後使用してはいけない" というクエリであり, あるクエリの前までに使用できなくなった辺は後のクエリでも使用できないままとする. それぞれのクエリを実行した後に, ある葉の頂点から頂点 1 までのパスのコストの和の最小値を出力せよ. ただし, どの葉の頂点からも頂点 1 に辿りつけない場合は −1 を出力せよ.
制約
すべての入力データは以下の制約を満たす.
- 3≦N≦10^5
- 1≦Q≦N−1
- 1≦w_i≦10^3
- 2≦x_i≦N
また,この問題には部分点が設定されており,1 点分の入力データは追加で以下の制約を満たす.
- N≦10^3
入力
N Q p_2 w_2 p_3 w_3 : p_N w_N x_1 x_2 : x_Q
出力
i(1≦i≦Q) 行目に,i 番目の情報の後での最短ルートの距離を出力せよ.ただし,山頂にたどり着けない場合は -1 を出力せよ.
入力例1
10 5 1 5 2 6 2 3 1 2 5 1 5 8 7 2 7 2 2 9 4 6 3 7 2
出力例1
3 11 12 14 -1
図は以下の通りとなる.
Problem: ey429
Tester: kyuridenamida, kagamiz, japlj