题目描述

U 国有 $n$ 栋建筑，其中第一栋是避难所，它们被 $n-1$ 条道路相连通着。建筑中都分别有一定数量的难民，初始，第 $i$ 个建筑中的难民数量为 $a_i$。

在战争进行过程中，发生了 $q$ 次事件，有以下两种事件：

• 1 x y：第 $x$ 栋建筑中难民数量变为 $y$。

• 2 x：第 $x$ 栋建筑通往避难所的最近的那条道路改变了状态，如果原来通畅现在就封堵，反之通畅。刚开始每条道路都是通畅的。保证 $x \neq 1$。

每次事件之后你都需要输出有多少难民能够顺着通畅的道路到达避难所。

输入格式

第一行两个正整数 $n,q$。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示有一条边连接 $u,v$。

接下来一行 $n$ 个整数 $a_i$。

下面 $q$ 行，每行两个或三个整数表示一次事件。

输出格式

$q$ 行，每一行一个数表示答案。

4 6
1 2
2 3
3 4
1 1 1 1
1 2 2
2 4
2 2
1 4 10
2 4
2 2

5
4
1
1
1
14

9 15
1 2
1 3
3 4
3 5
4 6
3 7
7 8
7 9
5 65 70 8 1 500 18 21 180
2 7
1 3 200
2 3
1 6 300
2 6
1 9 100
2 7
2 6
1 4 20
2 2
2 3
1 2 9
1 7 0
2 3
2 2

649
779
70
70
70
70
70
70
70
5
665
665
647
5
14

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^5$，$0\leq a_i,y\leq 10^9$。

说明

翻译自 AGM 2022 Qualification Round J Shelters。