Safe Haven: Refugee Connectivity under Dynamic Road Conditions

In country U there are \(n\) buildings, numbered from 1 to \(n\). Building 1 is the designated refuge (避难所). The buildings are connected by \(n-1\) bidirectional roads in such a way that there is a unique simple path from any building to the refuge. Initially, building \(i\) has \(a_i\) refugees.

During a war, \(q\) events occur. There are two types of events:

• 1 x y: The number of refugees in building \(x\) is updated to \(y\).
• 2 x: The road that is closest to building \(x\) on the unique path from building \(x\) to the refuge (i.e. the road connecting \(x\) with its parent in the tree rooted at 1) toggles its state. If it was open, it becomes blocked; if it was blocked, it becomes open. It is guaranteed that \(x \neq 1\).

After each event, output the total number of refugees that can reach the refuge by travelling along only open roads.

Note: Initially all roads are open. A building is considered connected if there is a path from it to building 1 consisting exclusively of open roads. The answer after each event is the sum of refugees in buildings that are connected to building 1.

The state updates in this problem can be mathematically summarized as follows. Denote the state of the road connecting building \(x\) to its parent by \(f(x)\) where

[ f(x)= \begin{cases} 1, & \text{if the road is open},\ 0, & \text{if the road is blocked}. \end{cases} ]

Building \(x\) (with \(x>1\)) is connected if and only if \(f(x)=1\) and its parent's connectivity condition is satisfied.

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) separated by a space, representing the number of buildings and the number of events.

The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the initial number of refugees in each building.

Then follow \(n-1\) lines. Each of these lines contains two integers \(u\) and \(v\) representing a road connecting building \(u\) and building \(v\). It is guaranteed that these roads form a tree (i.e. there is a unique simple path between any two buildings).

Each of the next \(q\) lines represents an event in one of the following two formats:

• 1 x y — update the number of refugees in building \(x\) to \(y\).
• 2 x — toggle the state of the road connecting building \(x\) to its parent in the tree rooted at 1 (\(x \neq 1\)).

outputFormat

For each event, output a single line with one integer: the total number of refugees that are able to reach building 1 via a path composed entirely of open roads.

sample

3 5
10 20 30
1 2
1 3
2 2
1 3 100
2 2
2 3
2 3

40
110
130
30
130

</p>