問題
背景
沉迷于盆栽爱好的Ikuta君,通过巧妙地修剪枝条和施肥,可以熟练地制作盆栽。
因为Ikuta君施肥的方法非常高明,所以可以让特定的枝条变粗或变细。(请注意,这盆栽的枝条超越了次元,粗细值可能为负。)
另外,当觉得某盆栽太大时,可以剪掉该盆栽中最细的枝条(粗细值最低的枝条),将树 2 分成若干部分,剪下的树再重新种入盆中,形成新的盆栽。
你决定根据Ikuta君的盆栽培育计划,通过修剪操作来确定剪哪根枝条。
課題
给定一棵树。树的每条边都附有一个整数强度。
对这棵树,处理以下查询。
- 查询1:边 i , 整数 d 被给出。边i的强度为 d 只增加。边 i 如果边已经被删除,则不做任何处理。
- 查询2:边 i 被给出。边 i 所在的连通分量中,构成该分量的边中强度最低的边 j 输出为一行后,删除边 j (如果强度最低的边有多个,则删除边编号最小的边。)如果边 i 已经被删除则 -1 。
配点
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 是以表示强度的形式输入的。
制約
- 2 ≤ N ≤ 100,000
- 1 ≤ a_i, b_i ≤ N
- -100,000 ≤ c_i ≤ 100,000
- 1 ≤ Q ≤ 100,000
- 1 ≤ i ≤ N-1
- -10,000 ≤ d ≤ 10,000
- 输入的图是树。
部分点
针对此问题设置了部分分数。这个问题的测试用例 30 这些点还满足以下约束。
- 2 ≤ N ≤ 1,000
- 1 ≤ Q ≤ 1,000
出力
对查询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