All submissions for this problem are available.Chef is given a tree ($0$ being its root). Each node has value called its Version Number. Upgrade on subtree is increasing version of least value nodes in the subtree to version value in that subtree greater than those minimum value nodes. Cost of upgrade is difference between least node value and node value just greater than it. There are $three$ types of queries, query 1, query 2 and query 3. Query 1: Print Cost of Upgrade. Query 2: Perform Upgrade Query 3: Print Sum of all versions of subtree of node $v$. ###Input: - First line will contain $N$ $M$, number of nodes and number of queries. - Next line will have $N$ space separated node values $a[i] , i \in [ \,0,N-1] \,$ - Next $N-1$ lines depict edges in form of two space separated integers depicting vertices - Next $M$ lines are queries in form $u$ $v$ where $u$ is query type and $v$ is node. ###Output: For each query, output in a single line answer. Print $-1$ if $no$ upgrade possible for query $1$. ###Constraints - $1 \leq a[ \,i] \, \leq 10^9$ - $1 \leq N,M \leq 10^5$ ###Sample Input: 5 3 12 10 8 14 15 0 1 1 2 1 3 2 4 1 2 2 3 3 1 ###Sample Output: 7 47 ![Right Click and view](https://drive.google.com/file/d/140ZoxY6jvxIn00Q_QhXP_2HfOc9M1GR1/view?u...) ###EXPLANATION: - $Query 1:$ 15 - 8 $= 7$. 8 is least value node and 15 is just greater than it - $Query 2:$ Node 3 can't be upgraded as no subtree node has value greater than it. - $Query 3:$ Sum of subtree 1 is 10 + 8 + 14 + 15 $= 47$.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.