P6329 [Template] Centroid Decomposition Tree / Shockwave

This is a template problem, with no $rap$.

On a piece of land, there are $n$ cities. They are connected by $n-1$ undirected edges, forming a tree. The distance between two adjacent cities is $1$. The value of city $i$ is $value_i$. Unfortunately, earthquakes often happen on this land, and as time goes on, the values of cities may also change. You need to process $m$ operations online: `0 x k` means an earthquake happens, with the epicenter at city $x$ and an affected radius of $k$. All cities whose distance to $x$ is at most $k$ will be affected. The economic loss of this earthquake is the sum of the values of all affected cities. `1 x y` means the value of city $x$ becomes $y$. To ensure the online nature of the program, in each operation, $x$, $y$, and $k$ must be decrypted by XOR with the output of your previous query. If there has been no output before, the previous output is considered to be $0$ by default.

The first line contains two positive integers $n$ and $m$. The second line contains $n$ positive integers. The $i$-th number denotes $value_i$. The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating an undirected edge between $u$ and $v$. The next $m$ lines each contain three numbers, describing the $m$ operations.

Output several lines. For each query, output one positive integer per line as the answer.

#### Constraints For $100\%$ of the testdata, $1\leq n,m\leq 10^5$, $1\leq u,v,x\leq n$, $1\leq value_i,y\leq 10^4$, $0\leq k\leq n-1$. upd: The sample constraints are different from the real constraints. Please use the constraints given in the hint. #### Notes Source: BZOJ3730. Translated by ChatGPT 5