BZPRO
#5477. 星际穿越
内存限制：512 MiB
时间限制：15 Sec
提交
提交记录
讨论
题目描述
曾经有个星系其中有n个星球，有一颗恒星叫死星，其他行星以它为根构成一颗树。
其中死星的编号是1，其他行星编号为2～n。
每个星球有个发展程度为vi，一开始因为每个星球都至少有文明存在，所以初始的时候vi=1。
定义两个星球之间星际穿越的代价为路径上的发展程度之和，因为发展程度越高需要的过路费越高。
然后会有m次大事件发生，总共有两种类型。
技术爆炸：1 p x表示p号点的发展程度增加x。
技术交流：2 p 表示询问p子树内所有点对的星际穿越的代价之和(mod 10^9+7)。（点对的两点可以相同）
请输出每次技术交流的结果
输入格式
第一行两个正整数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
输出格式
对于每个技术交流的事件输出一行正整数表示答案。
样例
样例输入
5 5
1 2
1 3
3 4
3 5
2 5
2 1
1 2 3
2 2
2 3
样例输出
1
33
4
10
数据范围与提示
BZPRO