Summation over Tree Paths with Minimum Attribute Condition

We are given an undirected tree with (n) nodes numbered from 1 to (n). Each node (i) has two attributes: (t_i) and (v_i). For every ordered pair ((i, j)) (with (1 \le i, j \le n)), consider the unique simple path from node (i) to node (j). Let (x) be the node on this path that has the minimum (t) value (if there is more than one candidate, choose the one encountered first during the search). Define (f_{i,j}) as follows:

[ f_{i,j} = \begin{cases} x, & \text{if } v_j \le v_x \le v_i, \ 0, & \text{otherwise.} \end{cases} ]

Your task is to compute the sum

[ \sum_{i=1}^{n} \sum_{j=1}^{n} f_{i,j} ,, ]

where, when adding (x) to the sum, use its 1-indexed value. Note that the tree is given as an unrooted tree.

inputFormat

The input begins with a single integer \(n\) representing the number of nodes in the tree.

The second line contains \(n\) space-separated integers \(t_1, t_2, ..., t_n\) representing the first attribute of each node.

The third line contains \(n\) space-separated integers \(v_1, v_2, ..., v_n\) representing the second attribute of each node.

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

outputFormat

Output a single integer, which is the computed sum \(\sum_{i=1}^{n}\sum_{j=1}^{n} f_{i,j}\).

sample

3
1 2 3
1 2 3
1 2
2 3

10