P7671 [GDOI2016] Zootopia Madness.

The original memory limit is 512 MB. --- Nick is a fox who makes a living in Zootopia by cheating and tricking others. Hurt by prejudice in his childhood, he gave up his dream. He was trapped by the rabbit Judy and forced to work with her on a case, getting involved in an unexpected conspiracy, and after many hardships they became partners. They exposed Deputy Mayor Bellwether the sheep’s plan and found that Bellwether framed carnivores and used poison to drive them mad. Bellwether was sent to prison, and Nick and Judy lived a peaceful life for a while. However, the story did not end there. Flash, the honest sloth who helped them check license plates at the DMV, was actually the mastermind behind the incident of framing carnivores. Flash mass-produced a large amount of the drug that drives carnivores mad and released it among the carnivores. Now, a large number of carnivores have been infected, and Zootopia has fallen into chaos. Police Chief Bogo the buffalo found Nick and hoped he could help. Fortunately, the Zootopia Federal Security Bureau was very forward-looking: they secretly placed a machine in every state. The machines can produce energy stones, which can restore carnivores to normal. Now Nick and Judy need to activate these machines.

**Note: We provide a formal statement at the end.** Zootopia is a federation with $N$ states, and the federation forms a tree. That is, there are $N-1$ undirected roads connecting the $N$ states, and all $N$ states are connected. The states are numbered $1,2,3,\dots,N$. Each state has exactly one machine. Starting from the moment after a machine is activated, it begins producing energy stones, producing one per unit time. An energy stone takes effect immediately when produced, and in each unit time it can save a certain number of carnivores. The types of energy stones produced by machines in different states may differ: in state $i$, the machine produces energy stones that can save $a_i$ carnivores per unit time. Nick and Judy do not have much time left, so they decide to split up. Nick starts from state $X$ and heads to state $Y$, traveling along the shortest path from $X$ to $Y$. Nick starts at time $0$ and moves one state every unit time. Each time he arrives at a state, Nick activates the machine there. Nick wants to know, during the time from when he leaves $X$ until he arrives at $Y$, how many carnivores are saved in total. Nick is hesitant about which route to choose, so he will ask you several queries, hoping that you, who are smarter than him, can help. While he is asking you, the situation in Zootopia is also changing. The Zootopia Federal Security Bureau can perform a modification operation $X,Y,\Delta$: it upgrades the machines in all states on the shortest path from $X$ to $Y$ (including states $X$ and $Y$). After the upgrade, the number of carnivores that the energy stones produced by these machines can save per unit time increases by $\Delta$. Of course, the sloth Flash will not sit still. He has a monitor that watches the machines in every state. Whenever any machine is upgraded, the monitor saves the current attributes $a_i$ of machines in all states. Flash can use a mysterious weapon to perform a rollback operation $X$, restoring the current machine attributes of all states to the state saved at the $X$-th time (where $X=0$ means the initial state before any upgrade). Note that saving happens only when a modification operation is executed. Now you are given $M$ operations in order. If an operation is a query, output how many carnivores are saved in total when Nick travels from $X$ to $Y$ under the current situation. Since the answer may be large, you only need to output it modulo $20160501$. Note that all $M$ operations are encrypted. **** **Formal statement**: You are given a tree with $N$ nodes. Then there are $M$ operations of three types: - `1 x y w`: add $w$ to the node weight of every node on the path from $x$ to $y$. - `2 x y`: a query. Let the set of nodes on the path from $x$ to $y$ be $S(x,y)$, and let the path length between nodes $p,q$ be $\text{dis}(p,q)$. Compute $\sum_{i\in S(x,y)}\sum_{j\le \text{dis}(i,y)}a_i\cdot j$. Output the answer modulo $20160501$. - `3 x`: restore the node weights of the whole tree to the state right after the $x$-th `1` operation. Online processing is required.

The first line contains $2$ integers $N,M$, indicating the number of nodes and the number of operations. The next $N-1$ lines each contain $2$ integers $u,v$, indicating that there is an edge between $u$ and $v$ in the tree. The next line contains $N$ integers, the initial values of $a_i$ for the machines in the $N$ states. The next $M$ lines each start with a number indicating the operation type: - Type 1: a modification operation, followed by $3$ integers $X',Y',\Delta$. - Type 2: a query operation, followed by $2$ integers $X',Y'$. - Type 3: a rollback operation, followed by $1$ integer $X'$. Here $X',Y'$ are encrypted numbers. The correct values are $X=X' \text{xor lastans},Y=Y' \text{xor lastans}$. Here $\text{lastans}$ is the answer of the previous `2` operation modulo $20160501$; if there has been no `2` operation before, then it equals $0$.

For each operation `2`, output one line containing the queried answer modulo $20160501$.

Constraints: For all data, $1\le n,m\le 10^5$, $1\le a_i,\Delta\le 10^5$, $1\le x,y\le n$. For $20\%$ of the data, $n,m\le 2000$. For another $20\%$ of the data, the tree is a chain and there is no operation `3`. For another $40\%$ of the data, the tree is a chain. Translated by ChatGPT 5