← 返回题目列表

AtCoder · tkppc2015_j

J. 努力吧! (工作!)

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

問題文

joisinoOnee-chan 发现自己坐在家里的电视机前。
你曾经梦想过吗?
然而,自从他开始看电视以来,似乎已经过去了相当长的时间,墙上的时钟显示距离上班还有一个小时。

幸运的是,Joisino工作的市政厅离她家很近。
于是,乔伊西诺姐姐悠闲地到了工作地点,突然被告知她被分配到了道路维护部门。

这个城市目前正在经历大量的城市发展,人们担心交通状况会因此而恶化。
因此,市政府决定让 Joisino Onee-chan 负责了解交通状况。

这个城市目前 有1个城市。
然而,由于城市发展,预计城市数量将会增加。
创建新城市时,该城市会选择一个现有城市并在其与新城市之间创建一条道路。
因此,在任何时候,城市的数量都是n按此顺序输出n-1书籍之路是存在的。
另外,第一个城市是一座城市。 它被称为0,i(1 ≦ i)创建的第一个城市是一座城市。 创建的第i、i(1 ≦ i)条道路称为道路 i。

还有,随着这个城市各个城市的人口变化,每条道路所需的时间也会发生变化。
此外,为了提高居民的便利性,有必要了解从一个城市到耗时最长的城市所需的时间。

在这种情况下,joisino-neechan 有一个关于该城市的查询。 给出了Q。
i(1 ≦ i ≦ Q)信息是以下三种类型之一。

  • 查询1...创建了一个新城市并且该城市为A_i和所需时间C_i由道路相连。
  • 查询2...路A_i所需的时间 更改为C_i。
  • 查询3...城市 我需要知道从A_i到花费最长时间的城市的旅行时间。

当问题3出现时,你必须回答它。

然而,这项工作实在是太繁琐了,如果你手动去做的话,你最终就会以工作为生。
所以 Joisino-nee-chan 决定创建一个程序来为我完成这项工作。


入力

输入是按以下格式从标准输入给出的。

Q
T_1 A_1 C_1
T_2 A_2 C_2
:
T_Q A_Q C_Q
  • 1行显示查询数量。 给出Q(1 ≦ Q ≦ 5*10^5)被给予
  • 2从线Q行i在线i个查询已写入,T_i(1 ≦ T_i ≦ 3),A_i(0 ≦ A_i ≦ 今ある都市の数-1),C_i用空格分隔。
  • T_i表示查询的类型。
  • T_i = 1当创建一个新城市时,该城市就成为一个城市。 代表他们是通过A_i和所需时间C_i(1 ≦ C_i ≦ 10^9)路连接起来的。
  • T_i = 2是路 这意味着它已更改为A_i所需的时间 更改为C_i(1 ≦ C_i ≦ 10^9)。
  • T_i = 3如果城市A_i表示需要知道到达耗时最长的城市的旅行时间。C_i可以忽略。另外,如果只有一个城市,则该答案将为 0。

配点

这个问题有部分要点。

  • 数据集 1 是 如果您遇到Q ≦ 10^4并正确回答,您将获得5分。
  • 数据集 2 没有额外的限制,正确的答案将为您赢得 155 分。

出力

输出为查询 行数与3一样多。
i在线i输出查询 3 的答案。
还在输出末尾包含换行符。


入力例1

6
1 0 10
1 1 7
3 1 0
2 2 5
1 0 17
3 0 0

出力例1

10
17

在这种情况下,将完成以下操作。

  • 由于查询1的类型是1,所以它是城市。1是一个新创建的城市 由道路0和所需时间10连接。
  • 由于查询2的类型是1,所以它是城市。2是一个新创建的城市 由道路1和所需时间7连接。
  • 由于查询3的类型是3,所以它是城市。 输出从1到花费最长时间到达的城市的旅行时间。在这种情况下,城市 当前往0时 输出10。 我锻炼
  • 由于查询4的类型是2, 更改为2所需的时间 更改为5。
  • 由于查询5的类型是1,所以它是城市。3是一个新创建的城市 由道路0和所需时间17连接。
  • 查询6的类型是3,所以它是城市。0到花费最长时间到达的城市的旅行时间。在这种情况下,城市 当前往3时 输出17。 我锻炼
此外,处理所有查询后,城市将如下图所示。


入力例2

7
3 0 0
1 0 10
2 1 15
1 0 7
1 2 5
1 2 8
3 0 0

出力例2

0
15

在这种情况下,将完成以下操作。

  • 查询1的类型是3,所以城市 输出从0到花费最长时间到达的城市的旅行时间。在这种情况下,没有其他城市,所以0。 我锻炼
  • 由于查询2的类型是1,所以它是城市。1是一个新创建的城市 由道路0和所需时间10连接。
  • 查询3的类型是2,所以1所需的时间 更改为15。
  • 由于查询4的类型是1,所以它是城市。2是一个新创建的城市 由道路0和所需时间7连接。
  • 由于查询5的类型是1,所以它是城市。3是一个新创建的城市 由道路2和所需时间5连接。
  • 由于查询6的类型是1,所以它是城市。4是一个新创建的城市 由道路2和所需时间8连接。
  • 由于查询7的类型是3,所以它是城市。0到花费最长时间到达的城市的旅行时间。在这种情况下,城市 当前往1和城市4时 输出15。 我锻炼
此外,处理所有查询后,城市将如下图所示。


入力例3

10
1 0 234
1 1 354
2 1 145
2 1 456
2 1 51
3 0 0
1 0 352
3 0 0
2 1 234
3 3 0

出力例3

405
405
940