Description

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

Input Format

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.

Output Format

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

2
1 2
10 20
1
0 1 5

2

Hint

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