You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一棵 $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 (伍一鸣)