# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Yet Another Xinversion !

By asifthegreat · Limits 1s, 256 MB

The problem statement is simple. You are given a rooted tree ($1$ is the root) and every node has a cost, say $C_i$. You have to perform $Q$ operations. Each operation can be one of the following types.

• Given $u, val$. you have to set $C_u = val$.
• Given $u$. You have to find the Xinversion of $u$.

Xinversion is almost similar to the inversion of an array. Xinversion of a node $x$ is the number of nodes $y$ inside the subtree of $x$ such that $C_y > C_x$.

## Input

In the first line you are given two integers $N$ ($1 \leq N \leq 10^5$) and $Q$ ($1 \leq Q \leq 10^5$) , the number of nodes and the number of operations respectively.

The next line will contain $N$ integers, $i^{th}$ integer represents $C_i$ ($1 \leq C_i \leq 10^9$).

Each of the next $N-1$ lines will contain two integers $u, v$ which means $u$ and $v$ are connected with an edge.

Each of the next $Q$ lines will contain one of the two types of operations:

• 1 u val
• 2 u

## Output

For every operations of type 2, print the Xinversion of $u$. For more clear idea, see the sample input-output section.

## Sample

InputOutput
5 5
1 2 3 4 5
1 2
2 3
2 4
3 5
2 1
2 2
1 3 1
1 4 1
2 1
4
3
2

### Statistics

81% Solution Ratio

YouKnowWhoEarliest, Apr '20

nuipqiunFastest, 0.1s

MamnoonSiamLightest, 12 MB

steinumShortest, 814B