← 返回题目列表

Codeforces · 1797/D

D. 李华和树

中文机器翻译题面 查看原题

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$$$。