Subtree Sum Queries

You are given a rooted tree with \(N\) nodes numbered from 1 to \(N\). Each node has an assigned integer value. The tree is given as an undirected graph with \(N-1\) edges, and the tree is rooted at node 1.

Your task is to answer \(Q\) queries. In each query, you are provided a node \(u\) and you must compute the sum of the values of all nodes in the subtree rooted at \(u\). The subtree of a node \(u\) is defined as \(u\) and all of its descendants in the tree.

Input/Output: In this problem, the input is given via standard input (stdin) and the output should be printed to standard output (stdout).

Note: Use an efficient algorithm such as depth-first search (DFS) to precompute the subtree sums.

inputFormat

The first line contains two space-separated integers (N) and (Q), where (N) is the number of nodes and (Q) is the number of queries. The second line contains (N) space-separated integers representing the values assigned to the nodes (in order from node 1 to node (N)). Each of the next (N-1) lines contains two space-separated integers (u) and (v) indicating that there is an edge between nodes (u) and (v). The last line contains (Q) space-separated integers, each representing a query node.

outputFormat

Output a single line containing (Q) integers, where each integer is the sum of the values in the subtree rooted at the corresponding query node, in the order the queries are given.## sample

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

21 15 3