東京大学プログラミングコンテスト2014

I - 盆栽


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

問題

背景

趣味の盆栽に没頭しているイクタ君は、枝の切り方と肥料の与え方を工夫し、上手に盆栽を作ることが可能である。 イクタ君は肥料の与え方がとてもうまいので、特定の枝を太くしたり、細くしたりできる。 (この盆栽の枝は次元を超越しており太さが負になりうることに注意してほしい。)
また、ある盆栽が大きすぎると思った時はその盆栽の枝のうち最も細い(太さの値が最も低い)枝を切って、木を 2 つに分け、切り取って別れた木はまた鉢に植え、新たな盆栽とする。 あなたは、イクタ君が盆栽を育てる計画をもとに、枝を切る操作でどの枝を切るかを特定することにした。

課題

木が与えられる。木の辺にはそれぞれ整数の強度が与えられている。
この木に対して、次のクエリを処理せよ。

配点

300

入力

入力は以下の形式で与えられる。

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}
Q
q_1
:
q_Q

入力の 1 行目に木の頂点数を表す整数Nが与えられる。
続く N-1 行に頂点 a_i, b_i とそれらを結ぶ辺の初期強度 c_i を表す 3 つの整数が与えられる。
N+1 行目に処理すべきクエリの数 Q 、続く Q 行にクエリの内容が以下のように書かれている
クエリ 1

1 i d
クエリ 2
2 i
i が辺の番号(入力の i 番目の辺)、 d は強度を表すという形で入力される。

制約

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

出力

クエリ2に対する答えをそれぞれ一行で出力せよ。


入力例1

5
1 3 3
2 3 3
3 4 3
4 5 3
7
1 2 4
1 1 1
1 3 -1
2 1
2 1
2 1
2 4

出力例1

3
1
-1
4

入力例2

6
2 1 -2
3 2 0
4 1 -1
5 4 0
6 2 0
6
2 4
2 3
2 4
1 2 4
1 2 0
2 3

出力例2

1
3
4
-1

Submit提出する