#P1501. [国家集训队] Tree II

[国家集训队] Tree II

题目描述

一棵 nn 个点的树,每个点的初始权值为 11
对于这棵树有 qq 个操作,每个操作为以下四种操作之一:

  • + u v c:将 uuvv 的路径上的点的权值都加上自然数 cc
  • - u1 v1 u2 v2:将树中原有的边 (u1,v1)(u_1,v_1) 删除,加入一条新边 (u2,v2)(u_2,v_2),保证操作完之后仍然是一棵树;
  • * u v c:将 uuvv 的路径上的点的权值都乘上自然数 cc
  • / u v:询问 uuvv 的路径上的点的权值和,将答案对 5106151061 取模。

输入格式

第一行两个整数 n,qn,q

接下来 n1n-1 行每行两个正整数 u,vu,v,描述这棵树的每条边。

接下来 qq 行,每行描述一个操作。

输出格式

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

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

提示

【数据范围】
对于 10%10\% 的数据,1n,q20001\le n,q \le 2000
另有 15%15\% 的数据,1n,q5×1041 \le n,q \le 5\times 10^4,没有 - 操作,并且初始树为一条链;
另有 35%35\% 的数据,1n,q5×1041 \le n,q \le 5\times 10^4,没有 - 操作;
对于 100%100\% 的数据,1n,q1051\le n,q \le 10^50c1040\le c \le 10^4

By (伍一鸣)