Dynamic Trees and Queries
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Given a directed tree with N nodes. You need to process M queries.
Each node has a key and a value, a node is referenced by its key. N nodes have keys from 0 to N-1.
Root always has the key equal to 0. Queries can be of the following 4 types:
1. Given a key of a node present in the tree, append a child node to it. The new node gets the smallest never-used positive integer as its key. The value of the new node will be given in the input.
2. Given a key of a node(call it A) present in the tree. Add value to the value of all the nodes present in the subtree rooted at A.
3. Given a key of a node(call it A) present in the tree. Remove the subtree rooted at A from the tree.
4. Given a key of a node(call it A) present in the tree. Output the sum of values of all the nodes in subtree rooted at A.
Input is encoded:
Keys in M Queries of the input are encoded in the following way:
Let SPECIAL = 0 initially. Whenever a query of the type 4 occurs, SPECIAL is updated to the result of that query. All the keys given in queries are encoded, in order to decode them you need to add SPECIAL to it.
That is, you are given encoded_key as input, to get key use the formula key = SPECIAL + encoded_key.
First line of input has N, the number of nodes.
Second line has N integers, the values of given N nodes respectively.
Then, N-1 lines follow, each has two integers u, v. which specifies an edge from u to v.
Next line contains a single integer M, the number of queries.
Each query consists of 2 lines, First line has the the type of query, second line is as follows:
For queries 1 and 2, there are two integers, first one represents the key of a node in tree, second one represents the value.
For queries 3 and 4, there is a single integer, which represents the key of a node in tree.
For each query of type 4, output the required answer.
- 1 ≤ N ≤ 10^5
- 1 ≤ M ≤ 10^5
- 0 ≤ u < N
- 0 ≤ v < N, u is not equal to v
- All the keys in the input are valid
- If the type of the query is 3, the the key is nonzero.
- All the rest numbers in the input are in the range [-1000, 1000]
Input: 2 10 20 0 1 4 4 0 1 -30 5 2 -30 1 4 -30
Output: 30 38
type = 4 encoded_key = 0
Initially SPECIAL = 0
key = encoded_key + SPECIAL = 0
value at 0 + value at 1 = 10 + 20 = 30 is the answer
Now SPECIAL is updated to 30
type = 1 encoded_key = -30 value = 5
SPECIAL = 30
key = encoded_key + SPECIAL = -30 + 30 = 0
So we add a child node(with the key = 2) to the node with the key 0, the child node gets the value of 5
Firstly, sorry for the mistake.
Old : Let SPECIAL = 0 initially. Whenever a query of the type 4 occurs, SPECIAL is increased by the result of that query.
New : Let SPECIAL = 0 initially. Whenever a query of the type 4 occurs, SPECIAL is updated to the result of that query.
|Tags||anudeep2011, data-structure, hard, may14, tree|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.