P11330 [NOISG 2022 Finals] Grapevine

Syrup 有一个巨大的葡萄藤。这个葡萄藤上共有 $N$ 片叶子，用 $1 \sim N$ 编号；这些叶子之间有 $N-1$ 条藤连接。第 $i$ 条藤连接第 $A_i$ 和第 $B_i$ 片叶子，长度为 $W_i$。换句话说，这些叶子和藤组成了一棵树。没有两个葡萄藤的两端相同，且这些叶子之间都可以相互到达。 Syrup 精通养护葡萄藤。他可以向一个叶子 $j$ **浇水**，使得这里飞速生长。如果这片叶子上还没有葡萄，那么浇完水后会立刻长出；如果已经有葡萄了，那么这个葡萄会因为水分过多而消失。 他也可以选择一条树枝，并**改变它的长度**。因为这个葡萄藤实在太大了，所以他需要站在叶子上，并快速**找到**离它距离最近的一个葡萄。 现在，刚刚经历过暴风雨的葡萄藤上没有葡萄。在这一周内，Syrup 打算进行 $Q$ 次以上操作，他想让你帮他快速回答出他的问题。

第一行，两个整数 $N,Q$； 接下来 $N-1$ 行，每行三个整数 $A_i,B_i,W_i$。 接下来 $Q$ 行，表示 $Q$ 个操作： - `1 q`：现在 Syrup 站在编号为 $q$ 的叶子上，他想找到离它最近的葡萄，请你输出这个最小距离。 - `2 u`：向编号为 $u$ 的叶子浇水。 - `3 a b w`：将第 $a$ 片叶子和第 $b$ 片叶子之间的树枝长度改为 $w$。

对于每个 `1` 操作，输出距离的最小值。如果当前没有任何一个葡萄，输出 `-1`。

**【数据范围】** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$0$|$0$|样例| |$1$|$6$|$N,Q\le2000$| |$2$|$14$|对于所有查询操作，保证 $q=1$| |$3$|$15$|整个葡萄藤是一颗完全二叉树，$A_i=\lfloor\frac{i+1}{2}\rfloor,B_i=i+1$| |$4$|$15$|在任意时刻整个葡萄藤上都最多只有一个葡萄| |$5$|$18$|所有 `2` 操作都在 `1` 和 `3` 操作之前，且对于所有 `3` 操作，$w=0$| |$6$|$32$|无| 对于 $100\%$ 的数据，$2 \le N \le 100000,1 \le Q \le 100000,1 \le A_i \not = B_i \le N,0 \le W_i \le 10^9$。