Background

"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.

Problem Description

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$.

Input Format

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$.

Output Format

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

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

Hint

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<4$, which is not the maximum.

In the third query, the time with the maximum damage is time $5$. The monsters in rooms $3$ and $5$ can both reach room $5$, so the answer is $a_3+a_5=8$.

Constraints

"This problem uses bundled testdata."

For $10\%$ of the testdata, $n,m \leq 2000$.

For another $10\%$ of the testdata, for every corridor $(x,y)$, the one-way door satisfies $x<y$.

For another $30\%$ of the testdata, there are no type 2 events.

For $100\%$ of the testdata, $1\leq n,m \leq 2\times 10^5$, $1\leq a_i\leq10^4$.

But dungeon ghosts are wall-phasing monsters ( ) ( ) ( ).

Would anyone really fill the dungeon with one-way doors.

Translated by ChatGPT 5