Maximum Path Sum in a Tree

You are given a tree with N nodes where each node has an associated integer value. The tree is undirected and connected. You are also given Q queries. In each query, you need to find the sum of the values along the unique simple path between two given nodes u and v.

Note: For a query with nodes u and v, let l be the lowest common ancestor (LCA) of u and v when the tree is rooted at node 1. The answer for the query is given by:

\(\text{answer} = \text{sum}[u] + \text{sum}[v] - 2 \times \text{sum}[l] + \text{value}[l]\)

where sum[x] is the sum of node values along the path from the root (node 1) to node x.

Your task is to output the answer for every query.

inputFormat

The input is given from standard input and has the following format:

N Q
v1 v2 ... vN
u1 v1
u2 v2
... (N-1 lines representing edges)
q1_u q1_v
q2_u q2_v
... (Q lines representing queries)

Where:

• N is the number of nodes in the tree.
• Q is the number of queries.
• v1, v2, ..., vN are the integer values associated with each node (1-indexed).
• Each of the next N-1 lines contains two integers representing an undirected edge between two nodes.
• Each of the next Q lines contains two integers u and v for which you need to calculate the path sum.

outputFormat

For each query, output a single line with the sum of the values along the simple path from u to v.

## sample

5 3
5 3 6 1 9
1 2
2 4
2 3
2 5
1 3
4 2
1 5

14
4
17

</p>