OpenJudge

1085:购物

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
262144kB
描述

Eert市共有N个车站,这N个车站由N-1条双向公路相连,任意一个车站都可以到达其他所有车站。最初坐车通过第i条公路所需的时间为tiEert市的任何任何工作、生活设施均设置在车站处。也就是说,公路中间不会是任何人的居住或工作场所。并且,车站i的居住人口为piEert市仅有一个市场,设置在1号车站处。Eert市有着特殊的地区划分规则:将市场看作根,则整座城市成为一棵有根树,这时称以i为根的子树为地区i(这里地区有层层嵌套的关系,是不是觉得很神奇?)。

Eert市民每天都必须在居住地和工作地之间坐车往返,并且在途中顺道去超市购物。也就是说,它们会在居住地到工作地路上到市场所需时间最少的一个车站处坐车去顺便购物,而我们把这个车站叫做中转车站。

对于一对车站(无序对,且这两个车站可以相同),我们定义偏远指数为:两车站人口之积乘以中转车站坐车到市场所需的时间。

对于地区i,它的偏远指数为:地区i中每对车站(与上面一致,是无序对,且两车站可以相同)的偏远指数之和。

Eert市的基本布局是不会改变的,人口分布和数量也不会改变。但是,政府会不时调整通过公路所需的时间即ti

你需要为政府开发一个程序以随时查询某一地区的偏远指数。


输入
第一行两个整数N,M,分别为车站个数和事件个数。
接下来一行N个整数,为人口pi。
接下来N-1行,每行三个整数ai,bi,ti,为公路连接的两个车站和初始时通过公路所需的时间。
接下来M行,每行描述一个事件,为以下两种之一(每种第一个数字为输入的时间类型):
1 a 询问地区a的偏远指数
2 a c 政府将通过公路a的时间改成了c
输出
对于每一个询问操作,输出一行一个整数为答案。因为答案可能很大,只需要输出偏远指数对取10^9+7模后的结果即可。
样例输入
5 4
1 2 3 4 5
1 2 10
1 3 10
1 4 10
2 5 10
1 1
1 2
2 1 20
1 1
样例输出
890
640
1280
提示
数据约束
对于100%的数据,1<=N,M<=100000, 1<=ti,pi,c<10^9+7。
提示
注意乘法溢出问题。
全局题号
7331
添加于
2014-08-24
提交次数
2
尝试人数
1
通过人数
1