logo AlgoBeat OnlineJudge
登录 注册

#214150. 雪月风花

内存限制:64 MiB 时间限制:1500 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

风雪飘摇落下,这白色的天地。

为了心底不可抹去的温暖啊,便让这纹路化作最后的羽翼。

直到我们再度相见,哪怕重新回到昨天。


伊正在帮助薰完成她的阵法。薰的阵法可以视作一棵 个节点的有根树,每个节点都有一个魔力阈值 与魔力等级 。初始时将会给出阵法的形态与薰为每个节点设定的 值。

接下来,伊将会对这个阵法进行几次测试并调整一些节点的 值,以使得这个阵法可以拥有足够的效率。

每一次测试时,伊都会指定一个源点 与范围 。定义本次测试消耗的能量为 ,定义 两点树上最短路径的边数。

但是这个值太大了,所以伊只需要你输出结果对 取模的值即可。

输入格式

第一行输入两个数

接下来 行,每行输入两个数 ,表示树上存在一条连接 的边。

接下来 行,第 行输入两个数表示

接下来 行,每行输入以下格式之一:

  • 1 x v,修改
  • 2 x v,修改
  • 3 x k,进行一次以 为源点、范围为 的测试,查询本次测试消耗的能量可能的最小值。

输出格式

对每次查询操作,输出一行一个数表示答案。

样例

样例输入 1

5 3
2 1
3 2
4 2
5 2
13 8
9 10
9 3
20 6
14 7
3 2 5
3 3 4
3 3 8

样例输出 1

74
104 
166

样例输入 2

4 4
2 1
3 2
4 3
10 7
5 3
7 2
8 5
1 1 4
1 4 6
1 2 4
3 4 10

样例输出 2

63

样例输入 3

6 6
2 1
3 2
4 1
5 1
6 1
9 6
8 6
2 5
5 1
10 1
5 8
1 3 3
3 5 2
2 2 5
2 2 10
1 6 7
3 2 3

样例输出 3

30
30

数据范围与提示

对所有数据,满足

::cute-table{tuack}

子任务编号 特殊性质 分值
#1
#2 ^
#3 AB
#4 ^ B
#5 C
#6

特殊性质 A:不存在 操作。

特殊性质 B:不存在 操作。

特殊性质 C:保证任意时刻