409615: GYM103643 R Quantum Fluctuations

Codicon has been hired as an assistant at a quantum physics research lab! The lab consists of $$$n$$$ rooms connected by $$$n - 1$$$ bidirectional passageways, so that every room is reachable from any other room. That is, the lab is a tree.

Codicon wants to place quantum particle generators in some rooms and then find out how much energy can be detected in other rooms. The lab is initially empty with no generators in any room. Each quantum generator emits particles that travel through the passageways such that exactly one particle reaches every other room. Quantum particles start off with no energy and gain $$$1$$$ unit of energy for every passageway they go through, but they also follow a curious rule. Due to quantum fluctuations, a particle will only be detected if it is an even distance away from the generator that created the particle.

Codicon conducts $$$m$$$ operations of two types. The $$$1$$$st type is adding $$$x_m$$$ quantum particle generators to a room $$$a_m$$$. The $$$2$$$nd type is a query, asking for the amount of energy detected in the room $$$a_m$$$.

The first line contains two numbers $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$ and $$$m$$$ $$$(1 \leq m \leq 5 \cdot 10^5)$$$.

The next $$$n - 1$$$ lines each contain two numbers, $$$a$$$ and $$$b$$$ describing a bidirectional passageway between rooms $$$a$$$ and $$$b$$$. $$$(1 \leq a, b \leq n)$$$

The next $$$m$$$ lines denote the operations. The first number of each line denotes the type of operation.

If the number is $$$1$$$, it is followed by two numbers $$$a$$$ and $$$x$$$, denoting that $$$x$$$ generators are added to room $$$a$$$. $$$(1 \leq a \leq n, 1 \leq x \leq 10^6)$$$

If the number is $$$2$$$, it is followed by a number $$$a$$$, representing a query for the amount of energy that will be detected in room $$$a$$$. $$$(1 \leq a \leq n)$$$

For $$$25\%$$$ of cases that count for points $$$(1 \leq n, m \leq 5000)$$$

For each operation of the $$$2$$$nd type, output a single number denoting the amount of energy detected in the queried room.

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

4
4

The $$$1$$$st operation adds $$$2$$$ generators to room $$$1$$$.

The $$$2$$$nd operation adds $$$2$$$ generators to room $$$2$$$.

For the $$$3$$$rd operation, room $$$4$$$ is distance $$$2$$$ away from room $$$1$$$, so each particle from room $$$1$$$ has energy $$$2$$$ when it reaches room $$$4$$$. Since there are $$$2$$$ generators in room $$$1$$$, there is $$$4$$$ energy detected total. Room $$$4$$$ is distance $$$1$$$ from room $$$2$$$, so the particles emitted from the generators in room $$$2$$$ aren't detected and don't add to the energy.

For the $$$4$$$th operation, room $$$3$$$ is distance $$$2$$$ away from room $$$2$$$, so the particles from the generators in room $$$2$$$ each have $$$2$$$ energy when they reach $$$3$$$, for a total of $$$4$$$ energy. Room $$$1$$$ is $$$1$$$ away so the particles from it aren't detected.

$$$---------------------------------------------$$$

Problem Idea: Mantlemoose

Problem Preparation: Mantlemoose

Occurrences: Advanced 12