問題文
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