Li Hua 有一个由 $$$n$$$ 个顶点和 $$$n-1$$$ 个边组成的树。树的根是顶点$$$1$$$。每个顶点 $$$i$$$ 的重要性为 $$$a_i$$$。将子树的大小表示为其中顶点的数量,将重要性表示为其中顶点重要性的总和。将非叶顶点的重儿子表示为具有最大子树大小的儿子。如果存在多个,则重子是索引最小的那个。
李华想要执行$$$m$$$操作:
- "1 $$$x$$$" ($$$1\leq x \leq n$$$) — 计算根为 $$$x$$$ 的子树的重要性。
- "2 $$$x$$$" ($$$2\leq x \leq n$$$) — 向上旋转 $$$x$$$ 的重子。形式上,将 $$$son_x$$$ 表示为 $$$x$$$ 的重儿子,将 $$$fa_x$$$ 表示为 $$$x$$$ 的父亲。他想要删除 $$$x$$$ 和 $$$fa_x$$$ 之间的边,并连接 $$$son_x$$$ 和 $$$fa_x$$$ 之间的边。保证$$$x$$$不是根,但不保证$$$x$$$不是叶子。如果$$$x$$$是叶子,请忽略该操作。
假设你是李华,请解决这个问题。
输入
第一行包含 2 个整数 $$$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$$$, $$$x_{j}\neq 1$$$ if $$$t_j = 2$$$) — 第 $$$j$$$操作。
输出
对于每个查询“1 $$$x$$$”,在独立行中输出答案。
示例
输入 #1
7 4 1 1 1 1 1 1 1 1 2 1 3 2 4 2 5 3 6 6 7 1 6 2 3 1 6 1 2
输出 #1
2 3 3
输入 #2
10 14 -160016413 -90133231 -671446275 -314847579 -910548234 121155052 -359359950 83112406 -704889624 145489303 1 6 1 10 10 8 1 4 3 4 2 7 2 5 3 2 9 8 1 4 2 2 2 4 1 4 1 10 2 10 1 9 1 6 2 8 2 10 1 5 1 8 1 1 2 5
输出 #2
-2346335269 -314847579 -476287915 -704889624 121155052 -1360041415 228601709 -2861484545
注意
在第一个示例中:
初始树如下图所示:
$$$6$$$子树的重要性是$$$a_6+a_7=2$$$。
将$$$3$$$(即$$$6$$$)的重子向上旋转后,树如下图所示:
$$$6$$$的子树的重要性是$$$a_6+a_3+a_7=3$$$。
$$$2$$$子树的重要性是$$$a_2+a_4+a_5=3$$$。