P10662 BZOJ4202 Stone Game

The Stone Game is a type of game that many people enjoy. This kind of game is usually related to moving stones and choosing whether to take them, and it often brings a lot of fun. There is a type of stone game on a tree with the following rules: on a rooted tree, each node has a certain number of stones. Two players take turns to play. Each turn, a player may move at most $m$ stones to the parent of a node, and in one turn they can only move stones from one node. Obviously, the root has no parent, so once a stone is moved to the root, it can no longer be moved. The question is: when playing this game on the subtree rooted at some node, does the first player have a winning strategy. To make the game harder, we make some small changes. Now, this tree may grow new nodes. Also, the number of stones on each node may change. Please answer: when playing this stone game on the subtree rooted at some node, does the first player have a winning strategy. This problem requires mandatory online processing.

The first line contains two integers $n, m$, meaning that initially there are $n$ nodes, and each move can move at most $m$ stones. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the initial number of stones, where node $1$ is the root. The next $n - 1$ lines each contain two integers $u, v$, indicating that there is an edge between $u$ and $v$. The next line contains a positive integer $t$, denoting the number of operations. The next $t$ lines each describe one operation. The first number of each line is the operation type: - If it is $1$, it is followed by an integer $v$, meaning to ask whether the first player must win when playing the game in the subtree of $v$. - If it is $2$, it is followed by two integers $x, y$, meaning to modify the number of stones at node $x$ to $y$. - If it is $3$, it is followed by three integers $u, v, x$, meaning to add a child $v$ to node $u$, whose initial number of stones is $x$.

For each query, output `Yes` if the first player must win; otherwise output `No`. Note: The testdata is processed with mandatory online handling. For each operation, except for the type number, all other numbers need to be XORed with the number of previous answers that are `Yes`.

For $100\%$ of the data, $1 \leq n, t \leq 5 \times 10^4$. Also, it is guaranteed that at any time, the number of nodes in the tree and the node indices will not exceed $10^5$. All other values are within the range of int. Translated by ChatGPT 5