「PA 2017」Banany

题目描述

题目译自 PA 2017 Runda 5 Banany

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

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

如果从 $s$ 到 $t$ 做生意，获得的利润是

一共有 $q$ 天。

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

输入格式

第一行输入两个整数 $n, q$ $(2 \leq n\leq 100\,000, 1\leq q \le 100\,000)$。

第二行输入 $n$ 个整数表示收益 $z_1 , z_2 , \dots , z_n$ $(1 \le z_i \le 10^{18})$。

接下来 $n - 1$ 行输入边权与费用 $a_i\ b_i\ c_i$ $(1\leq a_i,b_i\leq n, 1 \le c_i \le 10^{12})$。

接下来 $q$ 行，有两种输入。

1. 输入 $1\ v_i\ d_i$ $(1 \leq v_i \leq n, 1 \leq d_i \leq 10^{18})$ 表示将原本 $v_i$ 城市的费用替换为 $d_i$。
2. 输入 $2\ a_i\ b_i\ d_i$ $(1\leq a_i,b_i\leq n, 1 \le d_i \le 10^{12})$ 表示将原本连接 $(a_i, b_i)$ 两城市的边上的费用替换为 $d_i$。

输出格式

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

样例

样例 1

输入

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