Subtree swapping

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.
Input
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 w_{1}, w_{2}, ..., w_{N}, where w_{i} denotes the value assigned to node i at the beginning.
Each of the following N1 lines contains two space separated integers u and v denoting that there is an edge between u to v in the tree.
The ith of the following Q lines contains a description of the ith 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.
Output
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.
Constraints
 1 ≤ v, u ≤ N
 1 ≤ x ≤ 10^{5}
 1 ≤ w_{i} ≤ 10^{5}
Subtasks
Subtask #1: (10 points)
 1 ≤ N ≤ 1000
 1 ≤ Q ≤ 1000
Subtask #2: (20 points)
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 There are no queries of type 3
 Time limit is 4s
Subtask #3: (70 points)
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 Time limit is 5s
Example
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
Explanation
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:
<! initial drawing >
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:
<! drawings 2,3,4 > 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.
Author:  pkacprzak 
Tags  linkcuttree, ltime43, mediumhard, pkacprzak, sqrtdecomp, treap, tree 
Date Added:  29122016 
Time Limit:  2  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions