Tree and Queries
All submissions for this problem are available.
You are given a rooted tree with N nodes. Tree is rooted at node 1. Each node of the tree contains some value. Initially value of each node will be given.
You are given Q queries. Queries can be of two types, type U and type Q.
- Type U: This query is represented by U x v, which means that you
have to add value v to node x.
- Type Q: This query is represented by Q x, which means that you
have to output number of nodes in the subtree rooted at node x having value equal to zero.
First line of the input contains two space separated integers N and Q.
For next N - 1 lines, each line contains two space separated integers u, v
denoting that there is an edge between u and v in the tree. It is guaranteed that 1 ≤ u, v ≤ N, u != v.
It is also guaranteed that no edge is repeated in the input.
Next line contains N space separated integers denoting the initial weight of each node in order, 1 to N. Weights will be between -10^9 to 10^9 (both inclusive).
For next Q lines, each line contains a query of either type U or type Q.
For each query of type Q, output a single line containing an integer corresponding to answer of the query.
- 1 ≤ N, Q ≤ 10^5
- For query of type U, -10^9 ≤ v ≤ 10^9
- For query of type U and V, 1 ≤ x ≤ N
Input: 4 3 1 2 1 3 2 4 5 -2 0 3 Q 1 U 3 1 Q 1 Output: 1 0
|Tags||admin2, dfs-order, iitk, tree, wpc1, wpc1401|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.