{"raw_statement":[{"iden":"background","content":">「地牢中回荡着尖叫声...」\n\n打完世花的 ac 进入地牢刷灵气……\n\n花后地牢十分险恶，ac 想在地牢里搭满单向门。\n\n[![](https://cdn.luogu.com.cn/upload/image_hosting/a1ewte9n.png)](https://www.bilibili.com/video/BV1jf4y1Z7RB)"},{"iden":"statement","content":"ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻**最多只会存在一个**，且**伤害为 $a_i$**。\n\n为了方便刷灵气，ac 在每个过道上建了一个单向门。\n\n每一秒会发生以下几个事件之一：\n\n1. 第 $x$ 个房间生成了一个怪。怪**不会穿墙**，只会顺着单向门方向移动。\n\n2. 第 $x$ 个房间生成的怪被 ac 的仆从干掉了。\n\n3. ac 想要挂机刷怪，于是他希望知道，如果从时刻 1 开始站在房间 $x$ 一直到当前时刻，受到伤害最多的一个时刻所受伤害是多少。\n\n这里定义一个时刻受到伤害为可以走到 ac 所在房间的怪的伤害值总和，“可以走到”定义为可以穿过若干条单向门到达 ac 的房间（若干可以为 $0$）。ac 非常强大，不会中途被怪打死。\n\n当然，ac 所在的位置**不会改变怪的刷新**和**仆从的行为**。\n\n#### 简化版题面\n\n一棵树，每个点有个点权，每条边有个方向。\n\n有个集合，一开始为空，三个操作：\n\n1. 在集合中加入一个点。\n2. 删除集合中的一个点。\n3. 给出一个点 $x$，询问集合中满足可以走到 $x$ 的点的点权之和的历史最大值。"},{"iden":"input","content":"第一行，两个整数 $n,m$，分别表示房间个数和事件个数。\n\n接下来一行，共 $n$ 个整数，第 $i$ 个数表示 $i$ 房间中怪的伤害 $a_i$。\n\n接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 与 $y$ 有一条过道，单向门方向为 $x\\rightarrow y$ 。\n\n接下来 $m$ 行，第 $i$ 行两个整数 $fl,x$，表示第 $x$ 号房间发生了 $fl$ 号事件。\n\n对于 $fl=1$ 的操作，保证 $x$ 号房间没有怪。\n\n对于 $fl=2$ 的操作，保证 $x$ 号房间有怪。"},{"iden":"output","content":"对每一个 $fl=3$ 的事件，输出一个整数表示答案，并用换行隔开。"},{"iden":"note","content":"#### 样例一说明\n第一个询问中，时刻 $1$ 存在怪的房间为 $\\{4\\}$，$4$ 号房间的怪可以走到 $1$ 号房间，因此答案为 $a_4=4$。\n\n第二个询问中，受到伤害最大的时刻为时刻 $1$，答案为 $a_4=4$。其中时刻 $5$ 存在怪的房间为 $\\{3,5\\}$，而 $5$ 号房间的怪走不到 $1$ 号房间，因此此时刻受到伤害为 $a_3=3<4$，不是最大值。\n\n第三个询问中，受到伤害最大的时刻为时刻 $5$，$3,5$ 号房间的怪均可走到 $5$，因此答案为 $a_3+a_5=8$。\n\n---\n\n#### 数据范围\n**「本题采用捆绑测试」**\n\n对于 $10\\%$ 的数据，$n,m \\leq 2000$。\n\n对于另 $10\\%$ 的数据，过道 $(x,y)$ 单向门满足 $x