P5237 Dynamic Cactus IV

Template problem.

There are $n$ vertices, numbered from $1 \sim n$. Vertex $i$ has a weight $w_i$. Initially, there are no edges. There are $m$ operations. An operation is considered valid if, after applying it, every connected component of this undirected graph is a cactus, and there are no self-loops. Otherwise, the operation is invalid. Invalid operations are ignored. There are six types of operations: 1. Add an edge of weight $w$ between vertices $v$ and $u$. 2. Delete an edge of weight $w$ between vertices $v$ and $u$. 3. Add $d$ to the weight of every vertex on the shortest path from vertex $v$ to vertex $u$. 4. Add $d$ to the weight of every vertex in the sub-cactus $u$, rooted at vertex $v$. 5. Query information about the shortest path from vertex $v$ to vertex $u$. Output two integers $min,\sigma$ separated by a space, representing the minimum vertex weight and the sum of vertex weights on the shortest path. If there is no path reachable, then $min=-1,\sigma =-1$. If the shortest path is not unique, then $min=-2,\sigma =-2$. 6. Query information about the sub-cactus $u$, rooted at vertex $v$. Output two integers $min,\sigma$ separated by a space, representing the minimum vertex weight and the sum of vertex weights in sub-cactus $u$. If $v$ and $u$ are not connected, then $min=-1,\sigma =-1$. The definition of the sub-cactus $u$ rooted at vertex $v$ is: after deleting the edges on all simple paths between $v$ and $u$, the connected component containing $u$.

The first line contains two positive integers $n,m$ separated by spaces, meaning there are $n$ vertices and $m$ operations in total. The next line contains $n$ positive integers. The $i$-th positive integer is $w_i$. The next $m$ lines each describe one operation. Each line starts with three integers: $opt_i,v_i,u_i$. If $opt_i \in \{ 1,2,3,4 \}$, then one more integer follows; otherwise, the line ends.

For operations $5$ and $6$, output the corresponding results.

Constraints For $100\%$ of the testdata, $1 \leq n \leq 50000, 1 \leq m \leq 250000$. It is guaranteed that in operations $1$ and $2$, $w$ satisfies $1 \leq w \leq 10000$, so computations involving edge weights will not exceed the range of a 32-bit signed integer. It is guaranteed that the initial $w_i$ does not exceed $10^9$, and that the sum of all $d$ in operations $3$ and $4$ does not exceed $10^9$. Translated by ChatGPT 5