Path Sum Queries on a Tree

You are given a tree with \( n \) nodes and \( n-1 \) edges. Each node is assigned a unique integer weight. Your task is to answer \( q \) queries. In each query, you are given two nodes, and you must compute the sum of the weights of all nodes on the unique path connecting them.

The path sum is defined as \( \sum_{v \in path(u,v)} w_v \), where \( w_v \) denotes the weight of node \( v \), including both endpoints of the path.

inputFormat

The first line contains two integers ( n ) and ( q ), representing the number of nodes and the number of queries respectively.\nThe second line contains ( n ) integers representing the weights of nodes 1 through ( n ).\nEach of the next ( n-1 ) lines contains two integers ( u ) and ( v ), indicating an undirected edge between nodes ( u ) and ( v ).\nEach of the next ( q ) lines contains two integers ( a ) and ( b ), representing a query that asks for the sum of node weights on the path between ( a ) and ( b ).

outputFormat

For each query, output a single line containing the sum of the weights along the path between the two specified nodes.## sample

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

8
11
9