树
题号：NC215082
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一个含有n个结点的树，1号点为根结点，有n - 1条边， 每个结点都有一个权值，现在你有3种操作：

1 u，表示询问以u为根结点的子树所有点的权值和。

2 u v，表示将以u为根结点的子树所有点的权值都加v。

3 u v，表示将以u结点的所有儿子结点权值都加v（包括u结点本身）。

输入描述:

第一行两个整数 n   q，表示n个结点，q次操作。

第二行n个整数，表示每个点的权值。

接下来n - 1行两个整数，u  v，表示u到v有一条无向边（保证数据构成一颗树）。

接下来q行，每行为题目描述提到的的3种格式之一，表示一次操作。

输出描述:

按照输入顺序，对于每个1操作，输出一行一个整数表示对应的和。
示例1

输入

复制 
7 5
1 1 1 1 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7
2 3 1
3 1 1
1 2
1 3
1 6

输出

复制 
4
7
2

备注:

对于的数据：，点权 ，，操作2，和操作3所加的权值  。

对于的数据：，点权  ，操作2，和操作3所加的权值 。