Background

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

Problem 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