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 (11 is the root) and every node has a cost, say CiC_i. You have to perform QQ operations. Each operation can be one of the following types.

  • Given u,valu, val. you have to set Cu=valC_u = val.
  • Given uu. You have to find the Xinversion of u u.

Xinversion is almost similar to the inversion of an array. Xinversion of a node xx is the number of nodes yy inside the subtree of xx such that Cy>CxC_y > C_x.


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

The next line will contain NN integers, ithi^{th} integer represents CiC_i (1Ci1091 \leq C_i \leq 10^9).

Each of the next N1N-1 lines will contain two integers u,vu, v which means uu and vv are connected with an edge.

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

  • 1 u val
  • 2 u


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


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



81% Solution Ratio

YouKnowWhoEarliest, Apr '20

nuipqiunFastest, 0.1s

MamnoonSiamLightest, 12 MB

steinumShortest, 814B


Login to submit


First find the euler path of the tree and then the rest of the problem is fairly easy. You can use a...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.