[国家集训队] Tree II

一棵 $n$ 个点的树，每个点的初始权值为 $1$。 对于这棵树有 $q$ 个操作，每个操作为以下四种操作之一： - `+ u v c`：将 $u$ 到 $v$ 的路径上的点的权值都加上自然数 $c$； - `- u1 v1 u2 v2`：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树； - `* u v c`：将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$； - `/ u v`：询问 $u$ 到 $v$ 的路径上的点的权值和，将答案对 $51061$ 取模。

第一行两个整数 $n,q$。 接下来 $n-1$ 行每行两个正整数 $u,v$，描述这棵树的每条边。 接下来 $q$ 行，每行描述一个操作。

对于每个询问操作，输出一行一个整数表示答案。

3 2
1 2
2 3
* 1 3 4
/ 1 1

4

【数据范围】 对于 $10\%$ 的数据，$1\le n,q \le 2000$； 另有 $15\%$ 的数据，$1 \le n,q \le 5\times 10^4$，没有 `-` 操作，并且初始树为一条链； 另有 $35\%$ 的数据，$1 \le n,q \le 5\times 10^4$，没有 `-` 操作； 对于 $100\%$ 的数据，$1\le n,q \le 10^5$，$0\le c \le 10^4$。 By (伍一鸣)