题目描述

有一棵点数为 $N$ 的树，以点 $1$ 为根，且树有点权。然后有 $M$ 个操作，分为三种：

1. 把某个节点 $x$ 的点权增加 $a$。
2. 把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$。
3. 询问某个节点 $x$ 到根的路径中所有点的点权和。

---

输入格式

第一行包含两个整数 $N,M$。表示点数和操作数。

接下来一行 $N$ 个整数，表示树中节点的初始权值。

接下来 $N-1$ 行每行两个正整数 $fr,to$， 表示该树中存在一条边 $(fr,to)$。

再接下来 $M$ 行，每行分别表示一次操作。其中第一个数表示该操作的种类（$1$ 到 $3$），之后接这个操作的参数。

• 对于类型 $1$：1 x a，表示把节点 $x$ 的点权增加 $a$。
• 对于类型 $2$：2 x a，表示把以节点 $x$ 为根的子树中所有点的点权都增加 $a$。
• 对于类型 $3$：3 x，表示询问节点 $x$ 到根的路径中所有点的点权和。

---

输出格式

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

---

样例

输入样例 1

5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

输出样例 1

6
9
13

样例解释

初始树结构（以 $1$ 为根）：

        1 (权值1)
       / \
      2   4 (权值4)
     / \
    3   5 (权值3) (权值5)

括号内为初始权值。

操作序列：

1. 3 3：询问节点 $3$ 到根的路径权值和，路径 $3 \to 2 \to 1$，权值和 $3 + 2 + 1 = 6$。
2. 1 2 1：节点 $2$ 权值增加 $1$，节点 $2$ 权值变为 $3$。
3. 3 5：询问节点 $5$ 到根的路径权值和，路径 $5 \to 2 \to 1$，权值和 $5 + 3 + 1 = 9$。
4. 2 1 2：以节点 $1$ 为根的子树中所有节点权值增加 $2$，即所有节点权值加 $2$，此时权值：$1$ 变为 $3$，$2$ 变为 $5$，$3$ 变为 $5$，$4$ 变为 $6$，$5$ 变为 $7$。
5. 3 3：询问节点 $3$ 到根的路径权值和，路径 $3 \to 2 \to 1$，权值和 $5 + 5 + 3 = 13$。

---

数据范围

• $N,M \le 10^5$
• 所有输入数据的绝对值都不会超过 $10^6$（包括权值和 $a$）。

时间限制：1000 ms
内存限制：524288 KB

---

提示

本题可以使用树链剖分或DFS序 + 线段树的方法。

由于询问的是节点 $x$ 到根节点的路径和，并且修改有单点加和子树加，我们可以利用 DFS 序将树转为线性结构：

• 对树进行 DFS，记录每个节点进入时间戳 $in[x]$ 和离开时间戳 $out[x]$。
• 以 $x$ 为根的子树在 DFS 序中对应区间 $[in[x], out[x]]$。
• 节点 $x$ 到根的路径无法直接对应一个区间，但我们可以用树状数组或线段树维护差分。

方法：建立两个树状数组（或线段树），一个维护“加标记”，一个维护“加标记乘以深度”的贡献。

具体地，设 $val[x]$ 为节点 $x$ 的权值，$dep[x]$ 为节点 $x$ 的深度（根深度为 $0$ 或 $1$ 均可，但公式需一致）。

对于子树加操作 $2\ x\ a$：在以 $x$ 为根的子树中每个节点权值增加 $a$，等价于在 DFS 序区间 $[in[x], out[x]]$ 上每个节点的权值加 $a$。
对于路径查询操作 $3\ x$：需要求 $\sum_{u \in path(x,1)} val[u]$。

我们可以用以下技巧：
在 DFS 序上，对节点 $u$ 的权值增加 $a$，等价于对 $u$ 的子树中所有节点到根的路径和增加 $a$（因为 $u$ 的子树中每个节点到根的路径都经过 $u$）。
因此，对于子树加操作 $2\ x\ a$，我们可以转化为：在树状数组上，将区间 $[in[x], out[x]]$ 的每个节点加上 $a$。
对于单点加操作 $1\ x\ a$，可以看作子树加 $a$ 但只影响 $x$ 一个节点，即区间 $[in[x], in[x]]$ 加 $a$。

那么查询 $x$ 到根的路径和时，只需要查询 $x$ 的子树对 $x$ 的贡献吗？不对。

另一种更直接的方法是：用树状数组维护差分。
定义 $b[i]$ 表示 DFS 序上第 $i$ 个位置对应的节点权值。
子树加操作：区间 $[in[x], out[x]]$ 加 $a$。
查询节点 $x$ 到根的路径和：需要计算 $\sum_{u \in path(x,1)} val[u]$。
我们可以维护两个树状数组 $c_1$ 和 $c_2$，其中：

• 对区间 $[l,r]$ 加 $a$ 时，在 $c_1$ 的 $l$ 处加 $a$，$r+1$ 处减 $a$；在 $c_2$ 的 $l$ 处加 $a \times (l-1)$，$r+1$ 处减 $a \times r$。
• 查询前缀和 $sum(x) = c_1$ 的前缀和 $\times x - c_2$ 的前缀和。

但是路径和并不是 DFS 序的前缀和，而是从根到 $x$ 的路径上所有节点的权值和。

因此，更简单的做法是：树链剖分。
用树链剖分将树剖分成链，每个节点有 DFS 序编号 $id[x]$。
对于子树加操作：子树在 DFS 序中是连续区间 $[in[x], out[x]]$，直接在线段树上区间加。
对于单点加操作：可以看作区间加的特殊情况。
对于路径查询操作：从 $x$ 向上跳到根，每次跳一条重链，查询该链上的区间和，累加即可。
由于查询总是到根，跳链的次数为 $O(\log n)$，每次线段树查询 $O(\log n)$，总复杂度 $O(\log^2 n)$，可以通过。

注意：本题也可以只用一个 DFS 序 + 线段树，但查询路径和时需要将路径拆成若干段，而因为总是查询到根的路径，可以更简单：在 DFS 序中，根到 $x$ 的路径并不连续，所以仍需用树链剖分跳链。

推荐：使用树链剖分，线段树维护区间和，支持区间加、区间求和。
操作：

• 1 x a：单点加，转化为区间 $[id[x], id[x]]$ 加 $a$。
• 2 x a：区间 $[in[x], out[x]]$ 加 $a$。
• 3 x：查询 $x$ 到根路径上的节点权值和，用跳链的方式累加每条重链的区间和。

时间复杂度：$O((N+M) \log^2 N)$，对于 $10^5$ 数据可以接受。