CF1628E Groceries in Meteor Town

Mihai 住在一个经常遭遇流星风暴的小镇。这很烦人，因为 Mihai 有时需要去买菜，而被流星砸到可不好玩。因此，我们希望你找出一条去买菜最危险的路线，好让我们骗他走那条路。 小镇有 $n$ 栋建筑，编号从 $1$ 到 $n$。有些建筑之间有道路连接，并且任意两栋建筑之间恰好有一条简单路径。每条道路都有一定的流星危险等级。所有建筑都有杂货店，但 Mihai 只关心那些开着的杂货店。最初，所有杂货店都是关闭的。 你将得到 $q$ 个操作，操作分为三种类型： 1. 给定整数 $l$ 和 $r$，编号从 $l$ 到 $r$ 的建筑的杂货店开门（对于已经开门的建筑不做任何操作）。 2. 给定整数 $l$ 和 $r$，编号从 $l$ 到 $r$ 的建筑的杂货店关门（对于已经关门的建筑不做任何操作）。 3. 给定整数 $x$，请你求出从 $x$ 出发到任意一个开着的杂货店的简单路径上，所经过的道路中最大的流星危险等级是多少。如果不存在通往开着的杂货店的路径，则输出 $-1$。

第一行包含两个整数 $n$ 和 $q$（$2 \le n, q \le 3\cdot 10^5$）。 接下来 $n-1$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n,\, 1 \le w_i \le 10^9$），表示建筑 $u_i$ 和 $v_i$ 之间有一条双向道路，危险等级为 $w_i$。 保证这些边构成一棵树。 接下来 $q$ 行，每行描述一个操作，第 $j$ 行以整数 $t_j$ 开头（$1 \le t_j \le 3$），表示第 $j$ 个操作的类型。 如果 $t_j$ 为 $1$ 或 $2$，则该行还包含整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）。 如果 $t_j$ 为 $3$，则该行还包含整数 $x_j$（$1 \le x_j \le n$）。

对于每个类型为 $3$ 的操作（$t_j = 3$），输出一行，表示从 $x_j$ 出发到任意一个开着的杂货店的简单路径上，所经过的道路中最大的流星危险等级是多少。如果不存在这样的路径，则输出 $-1$。

 上图是样例输入对应的小镇示意图。 在第一个操作时，没有任何杂货店开门，因此从 $1$ 到任何开着的杂货店的路径上都没有边，所以答案是 $-1$。 在第二和第三个操作后，开着的杂货店集合为 $\{1\}$。从 $1$ 到 $1$ 的简单路径没有边，所以第三个操作的答案是 $-1$。 在第四个操作后，没有任何杂货店开门。 在第五和第六个操作后，开着的杂货店集合为 $\{5, 6\}$。在第六个操作中，有两条从 $x_j = 4$ 到开着的杂货店的路径：$4$ 到 $5$ 和 $4$ 到 $6$。其中最大危险等级出现在 $4$ 到 $6$ 的路径上，所以第六个操作的答案是 $4$。这条路径在图中用红色标记。 在后续操作后，开着的杂货店集合为 $\{5\}$。在第八个操作中，从 $x_j = 4$ 到开着的杂货店的唯一路径是 $4$ 到 $5$，路径上的最大危险等级为 $3$。这条路径在图中用绿色标记。 在第九个操作中，从 $x_j = 1$ 到开着的杂货店的唯一路径是 $1$ 到 $5$，路径上的最大危险等级为 $5$。这条路径在图中用蓝色标记。 由 ChatGPT 4.1 翻译