#2497. 「PA 2017」Banany

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

题目译自 PA 2017 Runda 5 Banany

Bajtazar 是一名商人,他每天会从自己所在的城市出发,到另一个城市去贩卖香蕉。每条道路都会有一定的过路费,而作为终点的城市能获得一定收益(注意:途经点没有收益)。而每过一天,就会有一条道路的费用发生变化,或者某个城市的收益发生变化。Bajtazar 想知道当他每一天醒来后,以哪个城市作为终点获得的利润最大,而次日他会从该城市继续出发。

n 个城市,由 n - 1 条道路连接,且互相都能到达。第 i 个城市有一个收益 z_i ,每条边有一个费用 w

如果从 s t 做生意,获得的利润是

z_t - \sum_{e \in \mathrm{Path}(s, t)} w(e)

一共有 q 天。

最初 Bajtazar 在 1 号城市。他每天经历了费用的变动后会前往下一个城市。他会选择获得利润最大的,如有多个相同则选择编号最小的,但他不能呆在原来的城市不走。

输入格式

第一行输入两个整数 n q

第二行输入 n 个整数表示受益 z_1 , z_2 , \dots , z_n

接下来 n - 1 行输入边权与费用 u\ v\ w

接下来 q 行,有两种输入。

  1. 输入 1\ i\ z_i 表示将原本 i 城市的费用替换。
  2. 输入 2\ u\ v\ w 表示将原本连接 (u, v) 两城市的边上的费用替换。

输出格式

对于每行变化,总共输出 q 组答案。表示经历变化之后, Bajtazar 的下一个目标。

样例

样例输入

4 4
10 20 30 50
1 2 5
2 3 7
2 4 57
1 3 28
1 1 25
2 3 2 1
2 2 4 13

样例输出

3 1 3 4

数据范围与提示

n, q \le 10^5 , 1 \le z_i \le 10^{18} , 1 \le w \le 10^{12}