Queries on Tree

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given a tree T with N nodes numbered 1 through N. Each node of the tree has a value; let's denote the value of node v by C_{v}. You are also given Q queries to process. There are two types of queries:
 1 U V W — add W to the value of each node on the path between nodes U and V (both inclusive)
 2 U V X — consider each node on the path between nodes U and V (both inclusive) whose value is ≥ X; compute the minimum of these nodes' values
Process the queries in the given order and compute the answer to each query of the second type.
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two spaceseparated integers N and Q.
 The second line contains N spaceseparated integers C_{1}, C_{2}, ..., C_{N}.
 N1 lines follow. Each of these lines contains two spaceseparated integers U and V denoting an edge connecting nodes U and V.
 The following Q lines describe queries. Each of them contains four spaceseparated integers type, U, V and either W (for type = 1) or X (for type = 2). Here, type denotes the type of the query.
Output
For each query of the second type, print a single line containing one integer — the minimum value ≥ X of a node on the given path which is, or 1 if no such value exists.
Constraints
 1 ≤ T ≤ 100,000
 1 ≤ N, Q ≤ 100,000
 0 ≤ C_{i} ≤ 10^{9} for each valid i
 1 ≤ type ≤ 2
 1 ≤ X ≤ 10^{14}
 1 ≤ W ≤ 10^{9}
 1 ≤ U, V ≤ N
 the graph described on the input is a tree
 1 ≤ sum of N over all test cases ≤ 100,000
 1 ≤ sum of Q over all test cases ≤ 100,000
Subtasks
Subtask #1 (43 points): there are no queries of the first type (type = 2 for each query)
Subtask #2 (57 points): original constraints
Example
Input: 1 5 5 10 15 20 15 10 1 2 1 3 2 4 2 5 2 5 3 3 1 2 5 10 2 1 4 4 1 5 2 17 2 1 5 100 Output: 10 10 1
Author:  mgch 
Tester:  lg5293 
Tags  decomposition, hard, ltime58, mgch, squareroot, supernode 
Date Added:  27032018 
Time Limit:  3.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, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions