409515: GYM103604 J Shelters

Some countries are more likely to face disasters than others - be it economic or natural. This country is very prone to natural disasters, so it has set in place an elaborate system which is meant to minimize the amount of casualties. There are $$$N$$$ houses placed in the shape of a tree, with $$$N-1$$$ roads. Initially, none of these roads are blocked. The first house also works as a shelter in case of natural disasters.

Two different kind of updates can be made to this system, namely:

• 1 x y - house x will now have y people;
• 2 x - the first road on the path from home x to the shelter is now switching its state, i.e. if it was previously blocked, it becomes unblocked, and vice versa.

To make sure that the system works as intended, its developers want to check the total number of people that can get from all houses to the shelter after every update. However, they are not the kind of competitive programmers that would implement Treaps at A.G.M., so they require your help.

The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), denoting the number of houses and the number of updates made to the system.

Then $$$N-1$$$ lines will follow. Each line will contain two integers $$$x$$$, $$$y$$$, meaning that there is a road between house $$$x$$$ and house $$$y$$$.

The next line will contain $$$N$$$ integers $$$x_i$$$ ($$$0 \leq x_i \leq 10^9$$$) representing the amount of citizens currently living in house $$$i$$$.

Lastly, $$$Q$$$ lines will follow. Each line will represent an update. According to the update type, this might either be:

• $$$1$$$ $$$x$$$ $$$y$$$, meaning that house $$$x$$$ will now host $$$y$$$ ($$$0 \leq y \leq 10^9$$$) people in total.
• $$$2$$$ $$$x$$$, meaning that the first road on the path from home x to the shelter is now switching its state.

The output shall contain $$$Q$$$ lines. On every line, print an integer $$$x_i$$$, denoting the number of people that can reach the shelter after update $$$q_i$$$ has been executed.

4 6
1 2
2 3
3 4
1 1 1 1
1 2 2
2 4
2 2
1 4 10
2 4
2 2

5
4
1
1
1
14

9 15
1 2
1 3
3 4
3 5
4 6
3 7
7 8
7 9
5 65 70 8 1 500 18 21 180
2 7
1 3 200
2 3
1 6 300
2 6
1 9 100
2 7
2 6
1 4 20
2 2
2 3
1 2 9
1 7 0
2 3
2 2

649
779
70
70
70
70
70
70
70
5
665
665
647
5
14