← 返回题目列表

AtCoder · utpc2014_i

I. 盆景

中文机器翻译题面 查看原题

問題

背景

沉迷于盆栽爱好的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