P1501 [National Training Team] Tree II

A tree with $n$ nodes, where each node’s initial weight is $1$. There are $q$ operations on this tree, each being one of the following four types: - `+ u v c`: Add a natural number $c$ to the weight of every node on the path from $u$ to $v$. - `- u1 v1 u2 v2`: Delete the existing edge $(u_1, v_1)$ from the tree and add a new edge $(u_2, v_2)$. It is guaranteed that after the operation it is still a tree. - `* u v c`: Multiply the weight of every node on the path from $u$ to $v$ by a natural number $c$. - `/ u v`: Query the sum of the weights of all nodes on the path from $u$ to $v$, and output the answer modulo $51061$.

The first line contains two integers $n, q$. Each of the next $n-1$ lines contains two positive integers $u, v$, describing one edge of the tree. Each of the next $q$ lines describes one operation.

For each query operation, output one integer per line as the answer.

Constraints - For $10\%$ of the testdata, $1 \le n, q \le 2000$. - For an additional $15\%$ of the testdata, $1 \le n, q \le 5 \times 10^4$, there are no `-` operations, and the initial tree is a chain. - For an additional $35\%$ of the testdata, $1 \le n, q \le 5 \times 10^4$, there are no `-` operations. - For $100\%$ of the testdata, $1 \le n, q \le 10^5$, $0 \le c \le 10^4$. By (Wu Yiming). Translated by ChatGPT 5