P5237 动态仙人掌 IV

模板题。

有 $n$ 个点，从 $1 \sim n$ 编号，第 $i$ 个点有一个权值 $w_i$，初始没有边。 有 $m$ 个操作，如果操作后，这个无向图的每个连通块都是个仙人掌，且不存在自环，那这个操作合法，否则不合法。不合法的操作忽略。一共有六种操作： 1. 在结点 $v,u$ 间连一条权值为 $w$ 的边； 2. 在结点 $v,u$ 间删掉一条权值为 $w$ 的边； 3. 把结点 $v$ 到结点 $u$ 的最短路上的每一个结点的权值都加上 $d$； 4. 把以结点 $v$ 为根，子仙人掌 $u$ 的每一个结点的权值都加上 $d$； 5. 查询结点 $v$ 到结点 $u$ 的最短路信息。 输出两个用空格隔开的整数 $min,\sigma$，分别代表最短路上点权的最小值、和。 如果没有路可到达则 $min=-1,\sigma =-1$。 如果最短路不唯一则 $min=-2,\sigma =-2$。 6. 查询以结点 $v$ 为根，子仙人掌$u$的信息。 输出两个用空格隔开的整数 $min,\sigma$，分别代表子仙人掌 $u$ 中点权的最小值、和。 如果 $v,u$ 不连通则 $min=-1,\sigma =-1$。 以结点 $v$ 为根，子仙人掌 $u$ 的定义是，删掉 $v$ 到 $u$ 之间的所有简单路径上的边之后，$u$ 所在的连通块。

第一行两个用空格隔开的正整数 $n,m$ 表示一共有 $n$ 个结点，$m$ 个操作。 接下来一行 $n$ 个正整数，第 $i$ 个正整数为 $w_i$。 接下来 $m$ 行，每行代表一个操作，每行前三个整数：$opt_i,v_i,u_i$ 若 $opt_i \in \{ 1,2,3,4 \}$ 则接下来再输入一个整数，否则此行结束。

对于操作 $5$、$6$，输出相应的结果。

【数据范围】 对于 $100\%$ 的数据，$1 \leq n \leq 50000, 1 \leq m \leq 250000$ 保证操作 $1$、$2$ 中的 $w$ 满足 $1 \leq w \leq 10000$，所以关于边权的计算不会超出 $32$ 位有符号整数范围。 保证初始的 $w_i$ 不超过 $10^9$，保证所有操作 $3$、$4$ 中的 $d$ 之和不超过 $10^9$。