P2166 Gty’s Super Girl Tree [Testdata Suspected Incorrect]

I once met you among the green hills, Leaning on a new bamboo staff, with purple cornels in your hair. Barefoot, you stepped through the boundless drizzling rain, Then picked up the drifting snowflakes of Yanchuan, falling like a mat... Gty, the godlike (xian) bull (chong), never lacks girls... He comes to a “girl tree” again and finds that each girl has a beauty value... Since Gty is very zhe♂xue and very ji♂zhi, he is only interested in girls whose beauty value is greater than a certain threshold. He wants to know the number of girls with beauty value greater than $x$ in a certain subtree. A girl’s beauty value may change... A new girl may appear on the tree... However... a branch may break. Thus, to Gty’s surprise, what lies before him becomes a forest made of girl trees...

Maintain a rooted tree with $n$ initial nodes (the root is $1$). Nodes are labeled $1$ to $n$, and each node has a weight $w_i$. The tree may become a forest. Support the following operations: - `0 u x` Query the number of values strictly greater than $x$ in the subtree rooted at $u$. - `1 u x` Set the weight of node $u$ to $x$. - `2 u x` Add a new node whose id is the current number of nodes plus $1$, with parent $u$ and weight $x$. - `3 u` Delete the edge between $u$ and its parent, and make $u$ the root of its connected component. **This problem is strictly online.** All input $u, x$ must be XORed with $\text{last}$ to get the real input, where $\text{last}$ is the previous query’s answer, and initially $\text{last} = 0$.

The first line contains a positive integer $n$, the initial number of nodes. The next $n - 1$ lines each contain two integers $u, v$, indicating an undirected edge in the tree. The next line contains $n$ integers $w_i$, the initial weight of each node. The next line contains a positive integer $m$, the number of operations. The next $m$ lines each describe one operation, as specified above.

For each operation with $\text{op} = 0$, output one line with a single integer, as described in the problem statement.

Constraints For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $1 \le u \le n$, $0 \le w_i, x < 2^{31}$. Translated by ChatGPT 5