Yet Another Xinversion !

asifthegreat BDYP & Duoblogger Home Qu...
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

Submit

Login to submit.

Statistics

81% Solution Ratio
YouKnowWhoEarliest, Apr '20
nuipqiunFastest, 0.1s
MamnoonSiamLightest, 12 MB
steinumShortest, 814B
Toph uses cookies. By continuing you agree to our Cookie Policy.