{"problem":{"name":"[THUPC 2023 初赛] 种苹果","description":{"content":"农夫种了一棵苹果树，树上结满了大大小小的苹果。夏天正是果树生长发育的大好时节，树上不断抽出新的枝条、结出新的苹果，已有的苹果也在不断长大。 为了观察和记录苹果的生长状况，以便对未来收获的行情有大致的估计，农夫进行了长时间仔细的观察和研究。在整个记录周期的最开始，树上一共结有 $n$ 个苹果，农夫将其编号为 $1\\sim n$ ，有 $n-1$ 条树枝连接这些苹果，每条树枝的两端都恰好挂有一个苹果","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9136"},"statements":[{"statement_type":"Markdown","content":"农夫种了一棵苹果树，树上结满了大大小小的苹果。夏天正是果树生长发育的大好时节，树上不断抽出新的枝条、结出新的苹果，已有的苹果也在不断长大。\n\n为了观察和记录苹果的生长状况，以便对未来收获的行情有大致的估计，农夫进行了长时间仔细的观察和研究。在整个记录周期的最开始，树上一共结有 $n$ 个苹果，农夫将其编号为 $1\\sim n$ ，有 $n-1$ 条树枝连接这些苹果，每条树枝的两端都恰好挂有一个苹果，使得整个苹果树成为一个名副其实的树形结构。农夫对每个苹果进行了一番价值估计，第 $i$ 个苹果的初始价值为 $a_i$ ，表示农夫此时摘下它并卖出的净收益，考虑到成本因素， $a_i$ 可能为负。\n\n在整个记录周期中，共发生了 $m$ 件值得记录的事件，所有的事件共分为以下几种类型：\n\n$1\\ u\\ v\\ w$：树上原本连接苹果 $u$ 和苹果 $v$ 的树枝中间结出了一个新的苹果。设原先树上共有 $k$ 个苹果，则此时变为 $k+1$ 个，农夫将新长出的苹果编号为 $k+1$ ，其价值为 $w$ 。原先连接苹果 $u$ 和 $v$ 的树枝也因此分裂成两条，一条连接苹果 $u$ 和 $k+1$ ，另一条连接苹果 $k+1$ 和 $v$；\n\n$2\\ u\\ w$：树上长出了一条新树枝和一个新苹果。设原先树上共有 $k$ 个苹果，则此时变为 $k+1$ 个，农夫将新长出的苹果编号为 $k+1$，其价值为 $w$。新树枝连接苹果 $u$ 和 $k+1$。\n\n$3\\ u\\ v\\ w$：树上一部分苹果的价值发生了变化。树上连接苹果 $u$ 和 $v$ 的一整段枝条（即树形结构上连接 $u$ 和 $v$ 的最短路径，包括 $u$ 和 $v$ 本身）上的所有苹果的价值均增加了 $w$ 。考虑到价值的变化也可能是由于营养不足或病虫害引起的，因此 $w$ 可能为负。\n\n$4\\ u\\ v\\ w$：农夫想在树上进行一次抽样调查来研究自己的可能收益。他定义价值不小于 $w$ 的苹果为“优质苹果”，并选择了树上连接苹果 $u$ 和 $v$ 的一整段枝条（含义同上），想统计一下这段枝条上的苹果中有多少个“优质苹果”。\n\n但由于苹果的数量是在太多了，农夫数不过来，便只好请你来帮忙。注意：由于农夫不能预测未来，因此你帮农夫时必须**强制在线**地回答问题。\n\n## Input\n\n第 $1$ 行： $2$ 个正整数 $n,m$。\n\n第 $2$ 行： $n$ 个整数 $a_i$。\n\n接下来 $n-1$ 行：每行两个正整数 $u_i,v_i$，依次描述初始时树上的所有树枝。\n\n接下来 $m$ 行，每行 $3$ 或 $4$ 个整数，按照时间顺序描述所有的事件，格式如题目描述中所述。\n\n为了体现强制在线性，设上一次 $4$ 事件的答案是 $lastans$ （最开始时 $lastans=0$），则所有事件中输入的 $u,v,w$ 都需要异或上 $lastans$ 才是真正的 $u,v,w$。\n\n## Output\n\n对于每个 $4$ 事件输出一行，一个非负整数，表示农夫此次调查的“优质苹果”数量。\n\n[samples]\n\n## Note\n\n#### 样例解释 1\n\n对于这组样例，去除强制在线后的数据如下：\n\n```\n5 6\n1 3 3 2 2\n1 2\n1 3\n2 4\n2 5\n4 3 4 2\n3 1 5 1\n4 3 4 2\n1 1 2 5\n2 6 3\n4 4 7 4\n```\n\n#### 数据范围\n\n对于所有数据， $n,m \\leq 2 \\times 10^5$，$|a_i|, |w|\\leq 10^9$，保证任意时刻涉及到的苹果编号均有意义，保证初始的 $n-1$ 条树枝构成树形结构，所有 $1$ 事件保证连接苹果 $u$ 和 $v$ 的树枝在事件发生时存在。\n\n#### 题目来源\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9136","tags":["2023","O2优化","分块","THUPC"],"sample_group":[["5 6\n1 3 3 2 2\n1 2\n1 3\n2 4\n2 5\n4 3 4 2\n3 2 6 2\n4 0 7 1\n1 5 6 1\n2 2 7\n4 0 3 0\n","3\n4\n2\n"]],"created_at":"2026-03-03 11:09:25"}}