P2137 Gty's Girl Tree

I once heard you amid the strings and songs. The clapboard's sound shatters, half like a scene from an opera. Dance pavilions and singing stages are blown away by the wind. Deep in the years, a wisp of lingering echo remains... Gty shen (xian) ben (chong) has never lacked girls... He came under a "girl tree" and found that each girl has a beauty value... Because Gty is very philosophical, he is only interested in girls whose beauty value is greater than a certain number. He wants to know how many girls in some subtree have beauty value greater than $k$. A girl's beauty value may change... A new girl may appear on the tree...

Maintain a rooted tree with $n$ nodes initially (the root is $1$), with node labels $1 \sim n$, and each node has a weight $w_i$. 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 node whose index is "current number of nodes in the tree + 1", with parent $u$ and weight $x$. This problem is strictly online. All input $u, x$ must be XORed with $\text{last}$ to obtain the actual input. Here $\text{last}$ is the answer to the previous query, with initial $\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$, representing 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 contain three integers $\text{op}, u, x$, describing one operation.

For each operation with $\text{op} = 0$, output one line containing an integer, as described above.

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