CF1797D.Li Hua and Tree

Li Hua has a tree of $n$ vertices and $n-1$ edges. The root of the tree is vertex $1$. Each vertex $i$ has importance $a_i$. Denote the size of a subtree as the number of vertices in it, and the importance as the sum of the importance of vertices in it. Denote the heavy son of a non-leaf vertex as the son with the largest subtree size. If multiple of them exist, the heavy son is the one with the minimum index.

Li Hua wants to perform $m$ operations:

• "1 $x$" ($1\leq x \leq n$) — calculate the importance of the subtree whose root is $x$.
• "2 $x$" ($2\leq x \leq n$) — rotate the heavy son of $x$ up. Formally, denote $son_x$ as the heavy son of $x$, $fa_x$ as the father of $x$. He wants to remove the edge between $x$ and $fa_x$ and connect an edge between $son_x$ and $fa_x$. It is guaranteed that $x$ is not root, but not guaranteed that $x$ is not a leaf. If $x$ is a leaf, please ignore the operation.

Suppose you were Li Hua, please solve this problem.

李华有一棵包含 $n$ 个顶点和 $n-1$ 条边的树，树根为顶点 $1$。每个顶点 $i$ 具有重要性 $a_i$。定义一个子树的大小为其所含顶点的数量，其重要性为其所含所有顶点的重要性之和。对于一个非叶子顶点，将其重儿子（heavy son） 定义为子树大小最大的儿子；若存在多个这样的儿子，则重儿子为其中编号最小者。

李华希望执行 $m$ 次操作：

• "1 $x$"（$1\leq x \leq n$）——计算以顶点 $x$ 为根的子树的重要性；
• "2 $x$"（$2\leq x \leq n$）——将 $x$ 的重儿子向上旋转（rotate up）。形式化地，记 $son_x$ 为 $x$ 的重儿子，$fa_x$ 为 $x$ 的父节点。该操作将删除边 $(x, fa_x)$，并添加边 $(son_x, fa_x)$。题目保证 $x$ 不是根节点，但不保证 $x$ 不是叶子节点；若 $x$ 是叶子节点，请忽略该操作。

假设你是李华，请解决此问题。

The first line contains 2 integers $n,m$ ($2\le n\le 10^{5},1\le m\le 10^{5}$) — the number of vertices in the tree and the number of operations.

The second line contains $n$ integers $a_{1},a_{2},\ldots ,a_{n}$ ($-10^{9}\le a_{i}\le 10^{9}$) — the importance of each vertex.

Next $n-1$ lines contain the edges of the tree. The $i$-th line contains two integers $u_i$ and $v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$) — the corresponding edge. The given edges form a tree.

Next $m$ lines contain operations — one operation per line. The $j$-th operation contains two integers $t_{j},x_{j}$ ($t_{j}\in {1,2}$, $1 \leq x_{j} \leq n$, $x_{j}\neq 1$ if $t_j = 2$) — the $j$-th operation.

第一行包含两个整数 $n,m$（$2\le n\le 10^{5},1\le m\le 10^{5}$）—— 分别表示树中顶点的数量和操作的数量。

第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots ,a_{n}$（$-10^{9}\le a_{i}\le 10^{9}$）—— 表示每个顶点的重要性。

接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i,v_i\le n$, $u_i\ne v_i$）—— 表示对应的边。所给的边构成一棵树。

接下来的 $m$ 行描述操作，每行一个操作。第 $j$ 个操作包含两个整数 $t_{j},x_{j}$（$t_{j}\in \{1,2\}$, $1 \leq x_{j} \leq n$, 若 $t_j = 2$ 则 $x_{j}\neq 1$）—— 表示第 $j$ 个操作。

For each query "1 $x$", output the answer in an independent line.

对于每个查询“1 $x$”，请在独立的一行中输出答案。

In the first example:

The initial tree is shown in the following picture:

The importance of the subtree of $6$ is $a_6+a_7=2$.

After rotating the heavy son of $3$ (which is $6$) up, the tree is shown in the following picture:

The importance of the subtree of $6$ is $a_6+a_3+a_7=3$.

The importance of the subtree of $2$ is $a_2+a_4+a_5=3$.

在第一个例子中：

初始树如下图所示：

节点 $6$ 的子树的重要性为 $a_6+a_7=2$。

将节点 $3$ 的重儿子（即节点 $6$）向上旋转后，树变为如下图所示：

此时节点 $6$ 的子树的重要性为 $a_6+a_3+a_7=3$。

节点 $2$ 的子树的重要性为 $a_2+a_4+a_5=3$。