「CGOI-3」灵气

>「地牢中回荡着尖叫声...」 打完世花的 ac 进入地牢刷灵气…… 花后地牢十分险恶，ac 想在地牢里搭满单向门。 [](https://www.bilibili.com/video/BV1jf4y1Z7RB)

ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻**最多只会存在一个**，且**伤害为 $a_i$**。 为了方便刷灵气，ac 在每个过道上建了一个单向门。 每一秒会发生以下几个事件之一： 1. 第 $x$ 个房间生成了一个怪。怪**不会穿墙**，只会顺着单向门方向移动。 2. 第 $x$ 个房间生成的怪被 ac 的仆从干掉了。 3. ac 想要挂机刷怪，于是他希望知道，如果从时刻 1 开始站在房间 $x$ 一直到当前时刻，受到伤害最多的一个时刻所受伤害是多少。 这里定义一个时刻受到伤害为可以走到 ac 所在房间的怪的伤害值总和，“可以走到”定义为可以穿过若干条单向门到达 ac 的房间（若干可以为 $0$）。ac 非常强大，不会中途被怪打死。 当然，ac 所在的位置**不会改变怪的刷新**和**仆从的行为**。 #### 简化版题面 一棵树，每个点有个点权，每条边有个方向。 有个集合，一开始为空，三个操作： 1. 在集合中加入一个点。 2. 删除集合中的一个点。 3. 给出一个点 $x$，询问集合中满足可以走到 $x$ 的点的点权之和的历史最大值。

第一行，两个整数 $n,m$，分别表示房间个数和事件个数。 接下来一行，共 $n$ 个整数，第 $i$ 个数表示 $i$ 房间中怪的伤害 $a_i$。 接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 与 $y$ 有一条过道，单向门方向为 $x\rightarrow y$ 。 接下来 $m$ 行，第 $i$ 行两个整数 $fl,x$，表示第 $x$ 号房间发生了 $fl$ 号事件。 对于 $fl=1$ 的操作，保证 $x$ 号房间没有怪。 对于 $fl=2$ 的操作，保证 $x$ 号房间有怪。

对每一个 $fl=3$ 的事件，输出一个整数表示答案，并用换行隔开。

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

4
4
8

8 7
4 1 3 5 8 6 2 9
1 2
3 1
4 2
5 1
5 6
7 5
6 8
1 1
1 5
3 7
3 1
1 2
2 5
3 5

0
12
8

#### 样例一说明 第一个询问中，时刻 $1$ 存在怪的房间为 $\{4\}$，$4$ 号房间的怪可以走到 $1$ 号房间，因此答案为 $a_4=4$。 第二个询问中，受到伤害最大的时刻为时刻 $1$，答案为 $a_4=4$。其中时刻 $5$ 存在怪的房间为 $\{3,5\}$，而 $5$ 号房间的怪走不到 $1$ 号房间，因此此时刻受到伤害为 $a_3=3<4$，不是最大值。 第三个询问中，受到伤害最大的时刻为时刻 $5$，$3,5$ 号房间的怪均可走到 $5$，因此答案为 $a_3+a_5=8$。 --- #### 数据范围 **「本题采用捆绑测试」** 对于 $10\%$ 的数据，$n,m \leq 2000$。 对于另 $10\%$ 的数据，过道 $(x,y)$ 单向门满足 $x<y$。 对于另 $30\%$ 的数据，不存在 2 事件。 对于 $100\%$ 的数据，$1\leq n,m \leq 2\times 10^5$，$1\leq a_i\leq10^4$。 ~~但是地牢幽魂就是穿墙怪（）（）（）~~ ~~不会真的有人会在地牢里搭满单向门吧。~~