P9136 [THUPC 2023 初赛] 种苹果

农夫种了一棵苹果树，树上结满了大大小小的苹果。夏天正是果树生长发育的大好时节，树上不断抽出新的枝条、结出新的苹果，已有的苹果也在不断长大。 为了观察和记录苹果的生长状况，以便对未来收获的行情有大致的估计，农夫进行了长时间仔细的观察和研究。在整个记录周期的最开始，树上一共结有 $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 对于这组样例，去除强制在线后的数据如下： ``` 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）初赛。 题解等资源可在 查看。