AT_k4pc_c 山登り(Mountain Climbing)

[problemUrl]: https://atcoder.jp/contests/k4pc/tasks/k4pc_c 岩井君はよく山に登る, 山登りのプロです(事実). 今日, 岩井くんは, 奇抜な形状をしていることで有名な窮理山への登山に挑戦します. 岩井君は窮理山の山頂まで登りたいです. また, 頂上で最高の眺めを楽しみ, できるだけ登山時に消耗する体力を減らすため, 岩井君はいつも山頂までたどり着くためのの最短ルートを使い登山をします. しかし窮理山ではよく土砂崩れが発生し, 道を通ることができなくなることがあります. さらにこの山は誰も管理していないので, 一度土砂崩れが起きるとその道を通ることは2度とできなくなります. 岩井君は山に登りに行く際, それまでに得られた土砂崩れの情報から, 登山コースを決めています. 山道の形と時系列順に並んだ土砂崩れの情報が与えられるので, それぞれの情報の後で利用できる最短ルートの距離を, コンピュータサイエンスの力で岩井君に教えてあげてください.

> $ 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 $ を出力せよ．

### 課題 $ 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 $ ### Sample Explanation 1 図は以下の通りとなる． !\[\](http://k4pc.contest.atcoder.jp/img/other/k4pc/C\_sample1.png)