P10799 "CZOI-R1" Triangles and Trees

CaiZi hates triangles, but he likes trees. 2024.8.15 Update: Added a set of hack testdata.

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$. 1. 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$.**

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.

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

**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