Background

CaiZi hates triangles, but he likes trees.

2024.8.15 Update: Added a set of hack testdata.

Problem Description

Given a tree with $n$ nodes, numbered from $1$ to $n$. Each node has a weight, and initially the weight of node $i$ is $a_i$. There are $q$ operations in total.

1. XOR the weights of all nodes on the simple path from node $x$ to node $y$ by $k$.
2. Determine whether it is possible to choose $3$ distinct nodes on the simple path from node $x$ to node $y$, and use the weights of these $3$ nodes as side lengths to form a triangle. In particular, if it is impossible to choose $3$ nodes, it is also considered impossible to form a triangle.

The simple path from node $x$ to node $y$ is the path from $x$ to $y$ that does not traverse any edge more than once. All nodes on it are the nodes on this path, including node $x$ and node $y$.

It is guaranteed that at any time, no node will have weight $0$.

Input Format

The first line contains $2$ integers $n, q$, representing the number of nodes in the tree and the number of operations.

The second line contains $n$ integers $a_i$, representing the initial weight of node $i$.

The next $n - 1$ lines each contain $2$ integers $u, v$, representing an edge of the tree.

The next $q$ lines each start with $1$ integer $s$, representing the operation type.

• If $s = 1$, then read $3$ integers $u, v, w$, representing an update operation.
• If $s = 2$, then read $2$ integers $u, v$, representing a query operation.

Output Format

For each query operation, output $1$ if the condition can be satisfied; otherwise output $0$. Output all answers consecutively, with no spaces or newlines.

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

0110

Hint

Sample Explanation

In the 1st operation, there are fewer than $3$ node weights on the simple path.
In the 2nd operation, the node weights on the simple path are $1, 2, 3, 4$.
After the 3rd operation, the node weights of nodes $1 \sim n$ are $5, 6, 7, 4, 1$.
In the 4th operation, the node weights on the simple path are $5, 6, 7$.
In the 5th operation, the node weights on the simple path are $1, 5, 6$.

Constraints

This problem uses bundled tests.

• Subtask #1 ($8\text{ pts}$): $n, q \le 3 \times 10^3$.
• Subtask #2 ($8\text{ pts}$): The tree is guaranteed to be a "chrysanthemum" (juhua).
• Subtask #3 ($20\text{ pts}$): In every update operation, $x = y$.
• Subtask #4 ($24\text{ pts}$): The tree is guaranteed to be a chain.
• Subtask #5 ($40\text{ pts}$): No special properties. Depends on Subtask #1 to Subtask #4.

For $100\%$ of the data, $1 \le u, v \le n \le 10^5$, $1 \le q \le 10^5$, $s \in \{1, 2\}$, and $1 \le a_i, w \le 2^{31} - 1$.

Translated by ChatGPT 5