Bacterial Reproduction

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/OCT19/hindi/BACREP.pdf), [Bengali](http://www.codechef.com/download/translated/OCT19/bengali/BACREP.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/OCT19/mandarin/BACREP.pdf), [Russian](http://www.codechef.com/download/translated/OCT19/russian/BACREP.pdf), and [Vietnamese](http://www.codechef.com/download/translated/OCT19/vietnamese/BACREP.pdf) as well. Chef has a rooted tree with $N$ vertices (numbered $1$ through $N$); vertex $1$ is the root of the tree. Initially, there are some bacteria in its vertices. Let's denote the number of sons of vertex $v$ by $s_v$; a leaf is a vertex without sons. During each second, the following events happen:  For each nonleaf vertex $v$, if there are $x$ bacteria in this vertex at the start of this second, they divide into $s_v \cdot x$ bacteria. At the end of this second, $x$ of these bacteria instantly move to each of its sons (none of them stay in vertex $v$). The original $x$ bacteria do not exist any more.  Zero or more bacteria appear in one vertex. These bacteria do not divide or move at this second. Initially, we are at the start of second $0$. You should process $Q$ queries ― one query during each of the seconds $0$ through $Q1$. There are two types of queries:  `+ v k`: During this second, $k$ bacteria appear in vertex $v$.  `? v`: Find the number of bacteria in vertex $v$ at the end of this second ― after the divided bacteria have moved. ### Input  The first line of the input contains two spaceseparated integers $N$ and $Q$.  Each of the next $N1$ lines contains two spaceseparated integers $x$ and $y$ denoting that vertices $x$ and $y$ are connected by an edge.  The next line contains $N$ spaceseparated integers $a_1, a_2, \ldots, a_N$ denoting the initial numbers of bacteria in vertices $1$ through $N$.  $Q$ lines follow. Each of these lines describes a query in the format `+ v k` or `? v`. ### Output For each query of the second type, print a single line containing one integer ― the number of bacteria in the given vertex. ### Constraints  $1 \le N, Q \le 5 \cdot 10^5$  $1 \le a_i \le 10^9$ for each valid $i$  $1 \le x, y \le N$  the graph described on the input is a tree  $1 \le v \le N$  $1 \le k \le 10^9$ ### Subtasks **Subtask #1 (20 points):** $1 \le N, Q \le 5,000$ **Subtask #2 (30 points):** $1 \le N, Q \le 10^5$ **Subtask #3 (50 points):** original constraints ### Example Input ``` 5 8 4 3 3 1 5 2 1 2 1 10 4 9 4 + 1 6 ? 3 + 3 5 ? 3 + 2 2 + 5 10 ? 5 ? 4 ``` ### Example Output ``` 6 0 33 25 ``` ### Explanation The numbers of bacteria in all vertices at the end of each second are:  $0$th second: $6, 1, 1, 13, 14$  $1$st second: $0, 6, 6, 14, 15$  $2$nd second: $0, 0, 5, 20, 21$  $3$rd second: $0, 0, 0, 25, 21$  $4$th second: $0, 2, 0, 25, 21$  $5$th second: $0, 0, 0, 25, 33$  $6$th second: $0, 0, 0, 25, 33$  $7$th second: $0, 0, 0, 25, 33$Author:  mikaeel 
Editorial  https://discuss.codechef.com/problems/BACREP 
Tags  fenwicktree, mediumhard, mikaeel, oct19, r_64, segmenttree, tree 
Date Added:  1082019 
Time Limit:  2 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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions