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 $N-1$ 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.
|Tags||dfs, difference-array, easy, euler-tour, icop1901, ista2000, lazy|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.