Unique Path Cost on a Geometric Tree

You are given a rooted tree drawn on the plane. The tree has n nodes labeled from 1 to n, with node 1 as the root. The depth of the root is 0, and for any node with depth x its y-coordinate is given by \(n-x+1\).

For each node, its children are arranged from left to right in increasing order of their labels. Every edge of the tree is drawn as a straight line segment connecting two nodes. In addition:

• Each leaf node has a ray extending infinitely downward (parallel to the \(y\)-axis),
• The root node has a ray extending infinitely upward (parallel to the \(y\)-axis),
• Every segment or ray is assigned a weight, and any two segments or rays intersect only at tree nodes.

You will be given q queries. Each query consists of two node labels \(u\) and \(v\). Starting from point \(u\) on the plane, you must reach \(v\) by moving along the drawn segments or rays. However, you are not allowed to pass through any other tree node except for \(u\) and \(v\). Each time you traverse an entire segment or ray, you incur a cost equal to its weight. Your task is to compute the minimum cost required to move from \(u\) to \(v\>.

Note: As every tree edge connects exactly two nodes and contains no other tree node on its interior, the only possible valid move between distinct tree nodes is to traverse an edge (or ray) directly connecting them. In other words, if \(u = v\) the cost is \(0\), if \(u\) and \(v\) are adjacent in the tree (the connecting segment or ray has endpoints \(u\) and \(v\)) then the answer is the weight of that segment (or ray), otherwise, no valid path exists (output \(-1\)).

inputFormat

The input is given as follows:

n q

where n is the number of nodes and q is the number of queries. Then for each node \(i\) from \(2\) to \(n\), there is a line containing two integers:

pi wi

Here, \(p_{i}\) is the parent of node \(i\), and \(w_{i}\) is the weight of the edge that connects \(p_{i}\) and \(i\>.

After that, there is a line with a single integer representing the weight of the upward ray from the root (node 1). Then there is a line containing L integers, where L is the number of leaf nodes (in increasing order of their node labels), representing the weights of the downward rays for each leaf.

Finally, there are q lines, each containing two integers:

u v

representing a query: find the minimum cost to move from node \(u\) to node \(v\) following the allowed moves.

outputFormat

For each query, output one line with a single integer: the minimum cost to move from \(u\) to \(v\) under the constraint that no other tree node (other than \(u\) and \(v\)) is passed. If \(u = v\), output \(0\). If \(u\) and \(v\) are directly connected by a segment (or ray), output the corresponding weight; otherwise, output \(-1\) if no valid path exists.

sample

5 5
1 3
1 4
2 2
2 5
7
6 1 8
1 1
1 2
2 1
2 4
3 5

0
3
3
2
-1

</p>