Do use segment tree#5839
Given a tree with (1 \leq n \leq 200\,000) nodes and a list of (1 \leq q \leq 100\,000) queries, process the queries in order and output a value for each output query. The given tree is connected, and each node has a weight w_i (-10\,000 \leq w_i \leq 10\,000).
Each query consists of a number t_i (t_i = 1 or ), which indicates the type of the query, and three numbers a_i, b_i, and c_i (1 \leq a_i, b_i \leq n, -10\,000 \leq c_i \leq 10\,000). Depending on the query type, perform one of the following actions:
- (t_i = 1: modification query) Change the weights of all nodes on the shortest path between a_i and b_i (both inclusive) to c_i. - (t_i = 2: output query) First, create a list of the weights on the shortest path between a_i and b_i (both inclusive), in order. Then, output the maximum sum of any non-empty continuous subsequence of the weights in the list. The value c_i is ignored for output queries.
The first line contains two integers and .
The second line contains integers: w_1, w_2, \ldots, w_n.
Each of the next n-1 lines contains two integers s_i and e_i (1 \leq s_i, e_i \leq n), indicating that there is an edge between s_i and e_i.
The next lines describe the queries, each containing four integers in the format described above. Queries must be processed in order from top to bottom.
For each output query, print the maximum sum on its own line.
Example 1