Tree Query

All submissions for this problem are available.
You are given a [tree](https://en.wikipedia.org/wiki/Tree_(graph_theory)) with $N$ vertices rooted at vertex $1$, where $ith$ vertex having a value $A_i$. You are also given $Q$ queries where each query gives you a node $u$ and a value $val$. You need to add $val$ to each node $v$ such that $v$ is in the subtree of $u$ ###Input:  First line will contain $N$ and $Q$, number of nodes and queries respectively.  Second line contains $N$ space separated integers, the initial value of each node.  Next $N1$ lines contain two integers $u$ and $v$ representing an edge between nodes $u$ and $v$.  The next $Q$ lines contain two integers each $u$ and $val$ as explained in the problem statement. ###Output: Output a single like containing $N$ space separated integers where the $ith$ integer denotes the value of the $ith$ node after all queries have been executed. ###Constraints  $1 \leq N, Q \leq 5 \times 10^5$  $1 \leq Ai, val \leq 10^5$  $1 \leq u \leq N$ ###Subtasks  20 points : $1 \leq N, Q \leq 1000$  80 points : Original constraints ###Sample Input: 5 3 1 1 1 1 1 1 2 1 3 3 4 3 5 1 1 2 3 3 2 ###Sample Output: 2 5 4 4 4 ###Explanation ![tree](https://i.imgur.com/wInPcia.png) Each node has an initial value of 1. The first query adds 1 to each node(since all nodes are in the subtree of node 1). Second query adds 3 to all nodes in subtree of node 2 and node 2 is a leaf so, it itself is the only node in its subtree. Third query adds 2 to all nodes in the subtree of node 3, namely nodes 3, 4 and 5.Author:  ista2000 
Editorial  https://discuss.codechef.com/problems/TREEUGH 
Tags  dfs, differencearray, easy, eulertour, icop1901, ista2000, lazy 
Date Added:  26062018 
Time Limit:  3 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 