4005. [模板]重链剖分

【题目描述】

给定一棵包含$n$个结点的树，每个结点有一个初始值。需要支持以下操作：

1 x y z，表示将$x$到$y$路径上的所有结点的值都加上$z$。

2 x y，表示求$x$到$y$路径上的所有结点的权值之和。

【输入格式】

第一行三个整数$n, m$，表示树的结点数、操作次数。

接下来一行$n$个整数，表示各个结点上的初始值。

接下来$n - 1$行，每行两个整数$x,y$，表示$x$和$y$之间有一条边。

接下来$m$行，每行一个操作。

【输出格式】

对于每个$2$操作，输出答案对$10^9 + 7$取余的结果。

【样例输入】

5 5
3 2 6 7 5
1 2
1 3
2 4
2 5
1 5 4 3
2 3 4
1 1 3 2
2 5 3
2 1 4

【样例输出】

24
26
20

【数据规模与约定】

对于$60\%$的数据，$1\le n, m\leq 1000$。

对于$100\%$的数据，$1\leq n, m\leq 10^5$，保证输入的所有权值在$[0, 2^{31}-1]$。