Problem Description

You are given an undirected tree with each node $i$ having two attributes $t_i$ and $v_i$.

Define the function $f_{i,j}$ for a directed path $i \to j$ as follows:
- If the node $x$ with the smallest $t_x$ on the path $i \to j$ satisfies $v_j \leq v_x \leq v_i$, then $f_{i,j} = x$.
- Otherwise, $f_{i,j} = 0$.

Calculate $\sum_{i=1}^n \sum_{j=1}^n f_{i,j}$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ space-separated integers, where the $i$-th integer represents $t_i$.

The third line contains $n$ space-separated integers, where the $i$-th integer represents $v_i$.

The next $n-1$ lines each contain two integers $a$ and $b$, indicating an edge between nodes $a$ and $b$ in the tree.

Output Format

Output a single integer, the answer to the problem.

Sample Input and Output

Sample Input #1

3
1 2 3
1 3 5
1 2
2 3

Sample Output #1

10

Sample Input #2

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

Sample Output #2

22

Notes

Sample #1 Explanation

• $f(1,1) = 1$
• $f(1,2) = 0$
• $f(1,3) = 0$
• $f(2,1) = 1$
• $f(2,2) = 2$
• $f(2,3) = 0$
• $f(3,1) = 1$
• $f(3,2) = 2$
• $f(3,3) = 3$

Thus, $\sum_{i=1}^3 \sum_{j=1}^3 f(i,j) = 10$.

Data Range

This problem has subtask bundling and subtask dependencies enabled.

For $100\%$ of the data, $t$ values are distinct, $1 \leq n \leq 10^5$, and $1 \leq t_i, v_i \leq 10^9$.

Special Condition $A$: Designate node $1$ as the root of the tree. For any pair of nodes $(x, y)$ where $x \neq y$, if $x$ is an ancestor of $y$, then $t_x < t_y$.

Special Condition $B$: For all $i \in [1, n)$, $a_i = i$ and $b_i = i+1$.

见题面 Input 部分

见题面 Output 部分