Tree Coloring with Leaf Constraints

Given a tree with n nodes (numbered from 1 to n), initially all nodes are white. You can color a node u black at a cost of \(w_u\). You are given q queries. Each query is given by three integers \(u\), \(l\), and \(r\). For each query, consider the tree rooted at node \(u\) (i.e. ignore the parent of \(u\) if any) and let a leaf be a node in this rooted tree having no children. For every leaf \(v\) in the rooted tree, you want to ensure that there exists at least one black node on the unique simple path from \(u\) to \(v\) if and only if \(l \le v \le r\) (i.e. the label of leaf \(v\) is in the inclusive range [\(l, r\])). Determine the minimum total cost needed to color some nodes black so that the condition is satisfied. If it is impossible, output -1.

Note: When a node is painted, its color remains black for that query; however, each query is independent (i.e. the tree is reset to all white nodes at the beginning of every query).

The mathematical formulation of the condition for every leaf \(v\) (in the tree rooted at \(u\)) is:

[ \text{There exists a black node on the simple path } \mathcal{P}(u,v) \iff l \le v \le r. ]

You are allowed to paint a node \(u\) (with cost \(w_u\)) even if some ancestor on the path is later painted; however, note that since \(u\) lies on every path from the root \(u\) to any leaf, if \(u\) is painted black then all leaves would have a black node on their path. Thus, if there is any leaf \(v\) such that \(v \notin [l,r]\) (i.e. a "non-required" leaf), then the root \(u\) must remain white in the final solution. Consequently, the selection of nodes to paint must be done on a branch-by-branch basis.

inputFormat

The first line contains two integers \(n\) and \(q\) separated by a space — the number of nodes in the tree and the number of queries.

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\), where \(w_i\) is the cost to paint node \(i\) black.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), denoting an undirected edge between nodes \(u\) and \(v\).

Each of the following \(q\) lines contains three integers \(u\), \(l\), \(r\) representing a query.

outputFormat

For each query, output a single line containing the minimum total cost required to achieve the desired coloring. If it is impossible to satisfy the condition, output -1.

sample

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

4
11
1