F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 5477. -- 星际穿越

5477: 星际穿越

Time Limit: 15 Sec  Memory Limit: 512 MB
Submit: 21  Solved: 13
[Submit][Status][Discuss]

Description

曾经有个星系其中有n个星球,有一颗恒星叫死星,其他行星以它为根构成一颗树。
其中死星的编号是1,其他行星编号为2~n。
每个星球有个发展程度为vi,一开始因为每个星球都至少有文明存在,所以初始的时候vi=1。
定义两个星球之间星际穿越的代价为路径上的发展程度之和,因为发展程度越高需要的过路费越高。
然后会有m次大事件发生,总共有两种类型。
技术爆炸:1 p x表示p号点的发展程度增加x。
技术交流:2 p 表示询问p子树内所有点对的星际穿越的代价之和(mod 10^9+7)。(点对的两点可以相同)
请输出每次技术交流的结果

Input

第一行两个正整数n,m。
接下来n-1行,每行两个数u,v表示u,v两颗行星在树上相连。
接下来m行,每行第一个数opt表示事件的类型。
然后根据opt=1,2有2,1个正整数。
pi ≤ n 且 vi < 10^9 + 7 
N,M<=2*10^5

Output

对于每个技术交流的事件输出一行正整数表示答案。

Sample Input

5 5
1 2
1 3
3 4
3 5
2 5
2 1
1 2 3
2 2
2 3

Sample Output

1
33
4
10

HINT

Source

By zjp_shadow

[Submit][Status][Discuss]

HOME Back