Tree Queries: Maximum Path Sum and Updates

You are given a tree with N nodes. Each node has an initial integer value. The tree is undirected and connected. You will be given Q queries. There are two types of queries:

• Type 1: 1 u v — Update the value of node u to v.
• Type 2: 2 — Compute the maximum path sum between any two nodes in the tree.

A path in the tree is defined as a sequence of nodes where each consecutive pair of nodes is connected by an edge. The path sum is the sum of the values of all nodes on the path. Note that the path does not necessarily need to pass through the root.

The answer to a query of type 2 is the maximum over all possible paths in the tree.

Note: After an update query, the new value is effective immediately for future queries. All queries are to be processed sequentially.

Hint: You can solve the maximum path sum problem with a DFS that tracks the two highest contributions from the child subtrees. Use the following recurrence:

$$\text{bestPath}(u) = A_u + \max(0, max_{child}\{gain\}) $$

and update the answer with

$$\text{ans} = \max(\text{ans}, A_u + \text{firstMax} + \text{secondMax}) $$

inputFormat

The input is given from the standard input in the following format:

N Q
A1 A2 ... AN
u1 v1
...
uN-1 vN-1
query1
...
queryQ

Where:

• N is the number of nodes in the tree.
• Q is the number of queries.
• The next line contains N integers representing the values at nodes 1 through N.
• The following N-1 lines each contain two integers u and v denoting an edge connecting node u and node v.
• The next Q lines each describe a query. A query of type 1 is given as 1 u v and a query of type 2 is given as 2.

outputFormat

For each query of type 2, output the maximum path sum in the current tree on a separate line to the standard output.

## sample

5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
2
1 3 10
2

15
22

</p>