Problem Description

A farmer planted an apple tree, and it is full of apples of all sizes. Summer is a great season for fruit trees to grow: the tree keeps growing new branches and new apples, and the existing apples keep getting bigger.

To observe and record the growth of the apples so that he can roughly estimate the future harvest profit, the farmer carried out long-term careful observation and research. At the very beginning of the whole recording period, there are $n$ apples on the tree. The farmer numbers them as $1 \sim n$. There are $n-1$ branches connecting these apples. Each branch has exactly one apple at each end, so the whole apple tree forms a true tree structure. The farmer also estimates the value of each apple: the initial value of the $i$-th apple is $a_i$, which means the net profit if he picks it and sells it at that moment. Due to costs, $a_i$ may be negative.

During the recording period, there are $m$ events worth recording. All events are of the following types:

$1\ u\ v\ w$: A new apple grows in the middle of the branch that originally connects apple $u$ and apple $v$. Suppose there were $k$ apples originally; then it becomes $k+1$. The farmer numbers the new apple as $k+1$, and its value is $w$. The original branch between $u$ and $v$ is split into two branches: one connects $u$ and $k+1$, and the other connects $k+1$ and $v$.

$2\ u\ w$: A new branch and a new apple grow on the tree. Suppose there were $k$ apples originally; then it becomes $k+1$. The farmer numbers the new apple as $k+1$, and its value is $w$. The new branch connects apple $u$ and $k+1$.

$3\ u\ v\ w$: The values of some apples change. The values of all apples on the whole branch segment connecting apple $u$ and apple $v$ (i.e., the shortest path between $u$ and $v$ in the tree structure, including $u$ and $v$ themselves) are increased by $w$. Since the change may also be caused by lack of nutrition or pests and diseases, $w$ may be negative.

$4\ u\ v\ w$: The farmer wants to conduct a sampling survey on the tree to study his possible profit. He defines apples with value at least $w$ as “high-quality apples”, and chooses the whole branch segment connecting apple $u$ and apple $v$ (same meaning as above). He wants to count how many “high-quality apples” are on this segment.

However, there are too many apples and the farmer cannot count them, so he asks you for help. Note: since the farmer cannot predict the future, you must answer the queries online.

Input Format

Line $1$: Two positive integers $n, m$.

Line $2$: $n$ integers $a_i$.

Next $n-1$ lines: Each line contains two positive integers $u_i, v_i$, describing all initial branches on the tree.

Next $m$ lines: Each line contains $3$ or $4$ integers, describing all events in chronological order, with the format as stated in the description.

To enforce online processing, let the answer to the previous type $4$ event be $lastans$ (initially $lastans = 0$). Then, in all events, the input $u, v, w$ must be XORed with $lastans$ to obtain the real $u, v, w$.

Output Format

For each type $4$ event, output one line with a non-negative integer, representing the number of “high-quality apples” in this survey.

5 6
1 3 3 2 2
1 2
1 3
2 4
2 5
4 3 4 2
3 2 6 2
4 0 7 1
1 5 6 1
2 2 7
4 0 3 0

3
4
2

Hint

Sample Explanation 1

For this sample, after removing the online XOR, the data is as follows:

5 6
1 3 3 2 2
1 2
1 3
2 4
2 5
4 3 4 2
3 1 5 1
4 3 4 2
1 1 2 5
2 6 3
4 4 7 4

Constraints

For all testdata, $n, m \leq 2 \times 10^5$, $|a_i|, |w| \leq 10^9$. It is guaranteed that any apple index involved at any time is valid. It is guaranteed that the initial $n-1$ branches form a tree structure. For all type $1$ events, it is guaranteed that the branch connecting apples $u$ and $v$ exists at the time the event happens.

Source

From the preliminary round of the 2023 Tsinghua University Student Programming Contest and Collegiate Invitational Contest (THUPC2023).

Resources such as solutions can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5