You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一棵包含 $n$ 个节点的无根树，节点编号为 $1 \sim n$。

这棵树的初始状态被称为 版本 0，每个节点 $i$ 都有一个初始的权值 $w_i$。

随后你需要处理 $q$ 次操作。

操作有两种方式：

• 操作1：基于版本 $t$，将树上节点 $u$ 到节点 $v$ 的简单路径上所有节点的权值增加 $y$，并生成一个新的版本。新产生的版本号为 当前存在的最大版本号 $+ 1$。
• 操作2：查询在版本 $t$ 中，树上节点 $u$ 到节点 $v$ 的简单路径上所有节点的权值之和。

简单路径：树上从 $u$ 到 $v$ 的最短路径。

输入格式

第一行包含两个整数 $n, q$，分别表示树的节点数和操作的次数。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$，表示初始时（版本 0）每个节点的权值。

接下来 $n-1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间存在一条无向边。

接下来 $q$ 行，每行第一个整数$op$。

• 若 $op=1$ ，代表操作1，随后输入四个整数 $t,u,v,y$。
• 若 $op=2$ ，代表操作2，随后输入三个整数 $t,u,v$。

输出格式

对于每一个 $op = 2$ 的操作2，输出一行一个整数，表示该查询的权值总和。

输入输出样例 #1

输入 #1

5 6
1 2 3 4 5
1 2
1 3
2 4
2 5
2 0 4 3
1 0 4 1 1
2 1 4 3
2 0 4 3
1 1 5 3 2
2 2 5 4

输出 #1

10
13
10
17

说明/提示

数据范围保证，$1 \le n, q \le 10^5$，$1 \le u, v \le n$，$-10^4 \le w_i, y \le 10^4$。

保证任何时刻 $0 \le t \le$ 当前最大版本号。

保证输入的树是合法的。