P10016 [CTT Mutual Test 2023] Rainbow

You are given a tree with $n$ nodes. - A set of nodes $S$ is called **connected** if and only if for all $u, v \in S$, every node on the simple path from $u$ to $v$ is also in $S$. - A set of nodes $S$ is called a **rainbow** of $[l, r]$ if and only if $S$ is **connected** and $S$ contains all nodes in $[l, r]$. - A set of nodes $S_0$ is called the **minimum rainbow** of $[l, r]$ if and only if $S_0$ has the smallest size among all **rainbows** of $[l, r]$. It can be proven that $S_0$ is unique. Each node has a weight. The weight of node $u$ is $w_u$. Initially, all node weights are $0$. Also, you are given a sequence $\{z_1, z_2, \cdots, z_n\}$. You are given $q$ commands. Each command is one of the following two types: - `1 l r`: Let $S_0$ be the **minimum rainbow** of $[l, r]$. For all $u \in S_0$, increase $w_u$ by $1$. - `2 l r u`: Compute $\left(\sum_{i=l}^r 19901991^{z_{\gcd(i,u)} w_i} \right) \bmod {20242024}$.

The first line contains two positive integers $n, q$. The second line contains $n$ non-negative integers, representing $z_1, z_2, \cdots, z_n$ in order. The next $n - 1$ lines each contain two positive integers $u, v$, describing an edge in the tree between $u$ and $v$. The last $q$ lines each contain $3$ or $4$ positive integers, describing a command. **Note: Each line in the input file ends with `\r`. Please filter it out by yourself.**

For each query (i.e. each command of the second type), output the answer.

**This problem uses bundled testdata**. For all testdata, it is guaranteed that: $1 \le n, q \le 8 \times 10^4, 0 \le z_i \le 10^9$. All commands satisfy $1 \le l \le r \le n, 1 \le u \le n$. **It is guaranteed that $(l, r)$ in the first type of commands are generated randomly**. The random generation method is as follows: - Randomly generate $l$ uniformly in $[1, n] \cap \mathrm{Z}$. - Randomly generate $r$ uniformly in $[1, n] \cap \mathrm{Z}$. - If $l > r$, swap $l$ and $r$. Constraints | Subtask ID | Score | $n \le$ | $q \le$ | Special Properties | Dependencies | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :----------: | | $1$ | $10$ | $10^3$ | $10^3$ | None | None | | $2$ | $20$ | $65536$ | $65536$ | A, B | None | | $3$ | $20$ | $65536$ | $65536$ | A | Depends on Subtask $2$ | | $4$ | $30$ | $65536$ | $65536$ | None | Depends on Subtasks $1, 2, 3$ | | $5$ | $20$ | $80000$ | $80000$ | None | Depends on Subtasks $1, 2, 3, 4$ | Special Property A: It is guaranteed that all commands of the second type appear after all commands of the first type. Special Property B: It is guaranteed that the number of commands of the second type is $\le 20$. Translated by ChatGPT 5