#P1501. [国家集训队] Tree II
[国家集训队] Tree II
题目描述
一棵 个点的树,每个点的初始权值为 。
对于这棵树有 个操作,每个操作为以下四种操作之一:
+ u v c
:将 到 的路径上的点的权值都加上自然数 ;- u1 v1 u2 v2
:将树中原有的边 删除,加入一条新边 ,保证操作完之后仍然是一棵树;* u v c
:将 到 的路径上的点的权值都乘上自然数 ;/ u v
:询问 到 的路径上的点的权值和,将答案对 取模。
输入格式
第一行两个整数 。
接下来 行每行两个正整数 ,描述这棵树的每条边。
接下来 行,每行描述一个操作。
输出格式
对于每个询问操作,输出一行一个整数表示答案。
3 2
1 2
2 3
* 1 3 4
/ 1 1
4
提示
【数据范围】
对于 的数据,;
另有 的数据,,没有 -
操作,并且初始树为一条链;
另有 的数据,,没有 -
操作;
对于 的数据,,。
By (伍一鸣)