P16451 rvtmpq

Given a tree with $n$ nodes, each node has two weights $a_i, b_i$. Define $f(S)$ as the smallest connected subgraph that contains the node set $S$. Then there are $q$ operations, each of the following forms: - Operation 1: Given $l, r, v$, let $S$ be the set formed by all numbers in $[l, r]$. For all $i \in f(S)$, add $v \times b_i$ to $a_i$. - Operation 2: Given $x$, query the value of $a_x$. - Operation 3: Given $x$, query the sum of $a$ values of all nodes on the path from $1$ to $x$. All answers are taken modulo $2^{32}$. The problem is strictly online.

The first line contains two integers $n, q$, representing the size of the tree and the number of operations. The second line contains $n$ integers, representing the array $a$. The third line contains $n$ integers, representing the array $b$. The next $n - 1$ lines each contain two integers $x, y$, representing an edge of the tree. The next $q$ lines each start with an integer $op$. If $op = 1$, then three integers $l, r, v$ follow, representing Operation 1. If $op = 2$, then one integer $x$ follows, representing Operation 2. If $op = 3$, then one integer $x$ follows, representing Operation 3. You need to XOR $l, r, v$ in Operation 1, $x$ in Operation 2, and $x$ in Operation 3 with the answer of the previous query operation $lasans$. In particular, if there is no query operation before this operation, then $lasans = 0$.

For each Operation 2 and Operation 3, output one line with the result modulo $2^{32}$.

Constraints: for $100\%$ of the testdata, $1 \le n \le 8 \times 10^5$, $1 \le q \le 3 \times 10^5$, and $0 \le l, r, v, x, a_i, b_i < 2^{32}$. It is guaranteed that after decryption, $l, r, v, x$ satisfy $1 \le l \le r \le n$, $0 \le v < 2^{32}$, and $1 \le x \le n$. Let $cnt_1$ be the number of operations with $op = 1$, $cnt_2$ be the number of operations with $op = 2$, and $cnt_3$ be the number of operations with $op = 3$. It is guaranteed that $\max(cnt_1, cnt_2, cnt_3) \le 0.6q$. Translated by ChatGPT 5