阿福正打算使用"老鼠偷奶酪"偷袭成龙, 却被小玉发现, 小玉说你不就是想要符咒吗, 这样你回答一个问题, 我就把符咒给你.
小玉有n个节点, 每个节点上都有对应的一个值. 现在小玉有q次询问, 询问格式如下:
1 x y z : x到y上的最短路径上的所有点的点权+z
2 x y : x到y上的最短路径上的所有点的点权开根号(向下取整)
3 x y : 输出x到y的最短了路径上的点权和
小玉说如果你把我的q次询问都回答正确, 我就把符咒给你, 怎么样? 阿福很想要这个符咒, 但是阿福不会这个问题, 你可以帮助他吗?
单组测试数据.
第一行两个整数n,q(0<n<=10000 0<q<=100000)分别代表节点数和小玉的q次询问.
接下来n-1行, 每行两个整数x, y. 代表节点x, y 之间存在一条边. (输入数据保证形成一棵树)
接下来一行有n个整数: 第i个数a[i]代表树上节点i的权值为a[i] (a[i]<=100000).
接下来q个询问, 格式如下:
1 x y z : x到y上的最短路径上的所有点的点权+z (0<x,y<=n)
2 x y : x到y上的最短路径上的所有点的点权开根号(向下取整) (0<x,y<=n)
3 x y : 小玉询问x到y的最短路径上的所有点的点权和, 阿福需要给出一个答复 (0<x,y<=n)
(以上所有数据保证在64位整型范围内)
对于每一个询问, 输出x到y的最短路径上的点权和
3 4 1 2 1 3 1 3 4 3 2 3 2 2 3 1 2 3 1 3 2 3
8 7