P8959 "CGOI-3" Aura

>"Screams echo through the dungeon..." After getting the AC for Shihua, ac enters the dungeon to farm aura... The post-flower dungeon is very dangerous, and ac wants to fill the dungeon with one-way doors. [](https://www.bilibili.com/video/BV1jf4y1Z7RB)

The dungeon in ac's world has $n$ small rooms, with exactly $n-1$ corridors, and all rooms are connected. In room $i$, at any time there is **at most one** monster spawned from this room, and its **damage is $a_i$**. To make aura farming easier, ac builds a one-way door on every corridor. Each second, one of the following events happens: 1. A monster spawns in room $x$. The monster **cannot pass through walls** and can only move along the direction of one-way doors. 2. The monster spawned in room $x$ is killed by ac's servant. 3. ac wants to AFK and farm monsters, so he wants to know: if he has been standing in room $x$ from time $1$ until the current time, what is the damage taken at the time when the damage was the maximum. Here, the damage taken at a time is defined as the sum of damage values of all monsters that can reach the room where ac is. “Can reach” means being able to pass through several one-way doors to arrive at ac’s room (the number of doors can be $0$). ac is very strong and will not be killed by monsters midway. Of course, ac’s position **does not change monster spawning** or **the servants’ actions**. #### Simplified statement A tree: each node has a weight, and each edge has a direction. There is a set, initially empty, and three operations: 1. Add a node to the set. 2. Delete a node from the set. 3. Given a node $x$, query the historical maximum of the sum of weights of nodes in the set that can reach $x$.

The first line contains two integers $n,m$, representing the number of rooms and the number of events. The next line contains $n$ integers, where the $i$-th integer represents the monster damage $a_i$ in room $i$. The next $n-1$ lines each contain two integers $x,y$, meaning there is a corridor between $x$ and $y$, and the one-way door direction is $x\rightarrow y$. The next $m$ lines each contain two integers $fl,x$, meaning event $fl$ happens in room $x$. For operations with $fl=1$, it is guaranteed that there is no monster in room $x$. For operations with $fl=2$, it is guaranteed that there is a monster in room $x$.

For each event with $fl=3$, output one integer as the answer, each on its own line.

#### Explanation for Sample 1 In the first query, at time $1$ the rooms with monsters are $\{4\}$. The monster in room $4$ can reach room $1$, so the answer is $a_4=4$. In the second query, the time with the maximum damage is time $1$, so the answer is $a_4=4$. At time $5$, the rooms with monsters are $\{3,5\}$, but the monster in room $5$ cannot reach room $1$, so the damage at this time is $a_3=3