Taco Enjoyment Calculation

Given a tree with \( n \) cities and \( n-1 \) roads connecting them, each city has an associated beauty score. The enjoyment of traveling between two cities \( u \) and \( v \) is defined as the sum of the beauty scores of all cities along the unique path connecting them.

More formally, if we let \( prefix[x] \) denote the cumulative sum of beauty scores from the root (which is city 1) to city \( x \), and let \( lca(u, v) \) denote the lowest common ancestor of \( u \) and \( v \) in the tree, then the enjoyment is computed by:

\( enjoyment(u,v) = prefix[u] + prefix[v] - 2 \times prefix[lca(u,v)] + beauty(lca(u,v)) \)

You are given \( q \) queries. For each query, calculate and output the enjoyment for the pair of cities provided.

inputFormat

The first line contains two integers \( n \) and \( q \) --- the number of cities and the number of queries.

The second line contains \( n \) integers, where the \( i\text{-th} \) integer represents the beauty score of city \( i \).

The following \( n-1 \) lines each contain two integers \( u \) and \( v \) indicating that there is a road connecting cities \( u \) and \( v \).

The next \( q \) lines each contain two integers \( u \) and \( v \), representing a query asking for the enjoyment value from city \( u \) to city \( v \).

outputFormat

For each query, output one integer on a new line --- the total enjoyment from traveling from city \( u \) to city \( v \).

## sample

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

16
11
8

</p>