题目描述

农夫种了一棵苹果树，树上结满了大大小小的苹果。夏天正是果树生长发育的大好时节，树上不断抽出新的枝条、结出新的苹果，已有的苹果也在不断长大。

为了观察和记录苹果的生长状况，以便对未来收获的行情有大致的估计，农夫进行了长时间仔细的观察和研究。在整个记录周期的最开始，树上一共结有 $n$ 个苹果，农夫将其编号为 $1\sim n$ ，有 $n-1$ 条树枝连接这些苹果，每条树枝的两端都恰好挂有一个苹果，使得整个苹果树成为一个名副其实的树形结构。农夫对每个苹果进行了一番价值估计，第 $i$ 个苹果的初始价值为 $a_i$ ，表示农夫此时摘下它并卖出的净收益，考虑到成本因素， $a_i$ 可能为负。

在整个记录周期中，共发生了 $m$ 件值得记录的事件，所有的事件共分为以下几种类型：

$1\ u\ v\ w$：树上原本连接苹果 $u$ 和苹果 $v$ 的树枝中间结出了一个新的苹果。设原先树上共有 $k$ 个苹果，则此时变为 $k+1$ 个，农夫将新长出的苹果编号为 $k+1$ ，其价值为 $w$ 。原先连接苹果 $u$ 和 $v$ 的树枝也因此分裂成两条，一条连接苹果 $u$ 和 $k+1$ ，另一条连接苹果 $k+1$ 和 $v$；

$2\ u\ w$：树上长出了一条新树枝和一个新苹果。设原先树上共有 $k$ 个苹果，则此时变为 $k+1$ 个，农夫将新长出的苹果编号为 $k+1$，其价值为 $w$。新树枝连接苹果 $u$ 和 $k+1$。

$3\ u\ v\ w$：树上一部分苹果的价值发生了变化。树上连接苹果 $u$ 和 $v$ 的一整段枝条（即树形结构上连接 $u$ 和 $v$ 的最短路径，包括 $u$ 和 $v$ 本身）上的所有苹果的价值均增加了 $w$ 。考虑到价值的变化也可能是由于营养不足或病虫害引起的，因此 $w$ 可能为负。

$4\ u\ v\ w$：农夫想在树上进行一次抽样调查来研究自己的可能收益。他定义价值不小于 $w$ 的苹果为“优质苹果”，并选择了树上连接苹果 $u$ 和 $v$ 的一整段枝条（含义同上），想统计一下这段枝条上的苹果中有多少个“优质苹果”。

但由于苹果的数量是在太多了，农夫数不过来，便只好请你来帮忙。注意：由于农夫不能预测未来，因此你帮农夫时必须强制在线地回答问题。

输入格式

第 $1$ 行： $2$ 个正整数 $n,m$。

第 $2$ 行： $n$ 个整数 $a_i$。

接下来 $n-1$ 行：每行两个正整数 $u_i,v_i$，依次描述初始时树上的所有树枝。

接下来 $m$ 行，每行 $3$ 或 $4$ 个整数，按照时间顺序描述所有的事件，格式如题目描述中所述。

为了体现强制在线性，设上一次 $4$ 事件的答案是 $lastans$ （最开始时 $lastans=0$），则所有事件中输入的 $u,v,w$ 都需要异或上 $lastans$ 才是真正的 $u,v,w$。

输出格式

对于每个 $4$ 事件输出一行，一个非负整数，表示农夫此次调查的“优质苹果”数量。

5 6
1 3 3 2 2
1 2
1 3
2 4
2 5
4 3 4 2
3 2 6 2
4 0 7 1
1 5 6 1
2 2 7
4 0 3 0

3
4
2

提示

样例解释 1

对于这组样例，去除强制在线后的数据如下：

5 6
1 3 3 2 2
1 2
1 3
2 4
2 5
4 3 4 2
3 1 5 1
4 3 4 2
1 1 2 5
2 6 3
4 4 7 4

数据范围

对于所有数据， $n,m \leq 2 \times 10^5$，$|a_i|, |w|\leq 10^9$，保证任意时刻涉及到的苹果编号均有意义，保证初始的 $n-1$ 条树枝构成树形结构，所有 $1$ 事件保证连接苹果 $u$ 和 $v$ 的树枝在事件发生时存在。

题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2023-Pre 查看。