All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given rooted tree with N weighted nodes numbered from 1 to N. The root of tree is node with number 1. Your goal is to handle Q queries, each of which can be one of the below three types:
- getSum(u) := returns sum of values in nodes in u's subtree.
- add(u, x) := adds x to values of every node in u's subtree (including u).
- swap(u, v) := swaps whole subtrees of u and v if and only if the subtrees are disjoint.
The first line of the input contains two space separated integers N and Q, denoting the number of nodes in the tree and the number of queries to handle, respectively.
In the second line there are N space separated integers w1, w2, ..., wN, where wi denotes the value assigned to node i at the beginning.
Each of the following N-1 lines contains two space separated integers u and v denoting that there is an edge between u to v in the tree.
The i-th of the following Q lines contains a description of the i-th query. It starts with integer qtype denoting the type of the query. If qtype=1, then it is followed by a single integer denoting the parameter of the query. Otherwise, if qtype=2 or qtype=3, it is followed by two space separated integers denoting the parameters to the query.
For each query of type 1, output the answer for such a query in a single line. Moreover, output -1 for each query of type 3 for which the given subtrees are not disjoint.
- 1 ≤ v, u ≤ N
- 1 ≤ x ≤ 105
- 1 ≤ wi ≤ 105
Subtask #1: (10 points)
- 1 ≤ N ≤ 1000
- 1 ≤ Q ≤ 1000
Subtask #2: (20 points)
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- There are no queries of type 3
- Time limit is 4s
Subtask #3: (70 points)
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- Time limit is 5s
Input: 10 5 1 1 1 1 1 1 1 1 1 1 1 2 1 3 1 8 3 4 8 9 8 10 4 5 4 6 4 7 2 8 1 1 3 3 4 8 1 3 3 1 2 Output: 5 7 -1
The input tree has 10 nodes and each of them has assigned value of 1 at the beginning. Initial tree can be drawn as follows:
There are 5 queries to handle. The first one adds a value of 1 to all nodes in subtree of 8. The second asks for the sum of values of nodes in subtree of 3, which is 5, because there are 5 nodes there, each with initial value of 1. The 3rd query swaps subtrees of nodes 4 and 8, which is performed as the below drawing illustrates:
This swap can be performed, because these subtrees are disjoint. The 4th query asks for the sum of values of nodes in subtree of 3. Now this subtree has changed and the result is 7, because there is one node with value 1 and 3 nodes with value 2 there. The last query tries to swap subtrees of 1 and 2, but since these subtrees are not disjoint, the answer for this query is -1.
|Tags||link-cut-tree ltime43 medium-hard pkacprzak sqrt-decomp treap tree|
|Time Limit:||2 - 5 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.