Eval
Prompt
### Problem: Persistent Dynamic Tree-Path Affine Transforms with Path-MEX Queries You are given a rooted tree $T$ containing $N$ vertices indexed from $1$ to $N$, with vertex $1$ initially designated as the root. Each vertex $v$ maintains an integer weight $w_v \in [0, P-1]$, where $P = 10^9 + 7$. Implement a persistent data structure in Rust capable of processing $Q$ online queries of four distinct operations efficiently under strict time and memory limits. --- ### Operations * **Type 1: Path Affine Transformation** `1 u v a b` For every vertex $x$ along the unique simple path between vertices $u$ and $v$ (inclusive), update its weight simultaneously: $$w_x \leftarrow (w_x \cdot a + b) \pmod P$$ * **Type 2: Dynamic Subtree Rerooting / Link-Cut** `2 u v` Detach the subtree rooted at vertex $u$ from its current parent and attach it as a direct child of vertex $v$. If $v$ is currently located inside the subtree rooted at $u$, this operation is invalid and must be ignored without altering the tree structure. * **Type 3: Path Minimum Excluded Value (MEX)** `3 u v` Calculate and return the smallest non-negative integer $k \ge 0$ such that $k$ does not appear in the multiset of weights along the simple path between $u$ and $v$. * **Type 4: Persistent State Rollback** `4 k` Revert the complete state of the tree structure and vertex weights to the exact state existing immediately after the completion of the $k$-th query ($0 \le k < \text{current query index}$). State $0$ corresponds to the initial configuration before any queries are executed. --- ### Constraints * $1 \le N \le 10^5$ * $1 \le Q \le 10^5$ * $0 \le w_v < 10^9 + 7$ for all $v \in [1, N]$ * $1 \le a, b < 10^9 + 7$ * Time Limit: **2.5 seconds** * Memory Limit: **512 MB** * All queries are encoded online: query parameters $u, v, k$ depend on the previous Type 3 query answer. --- ### Input Format * The first line contains two integers: $N$ and $Q$. * The second line contains $N$ space-separated integers representing the initial weights $w_1, w_2, \dots, w_N$. * The following $N - 1$ lines each contain two integers $u$ and $v$, denoting an initial undirected edge between vertices $u$ and $v$. * The subsequent $Q$ lines describe operations matching one of the four query formats. ### Output Format For each query of **Type 3**, output the resulting non-negative integer on a new line.
