Problem Description

You are given an unrooted tree. Each node $i$ has two attributes $t_i, v_i$.

Define $f_{i,j}$ for the directed path $i \to j$ as follows:

• If the node with the smallest $t_x$ on the path $i \to j$ is $x$, and $v_j \leq v_x \leq v_i$, then $f_{i,j} = x$.
• Otherwise, $f_{i,j} = 0$.

Compute $\sum\limits_{i=1}^n \sum\limits_{j=1}^n f_{i,j}$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers separated by spaces; the $i$-th integer denotes $t_i$ of node $i$.

The third line contains $n$ integers separated by spaces; the $i$-th integer denotes $v_i$ of node $i$.

The next $n - 1$ lines each contain two integers $a, b$, describing an edge $a \leftrightarrow b$ in the tree.

Output Format

Output one line with one integer, the answer.

3
1 2 3
1 3 5
1 2
2 3

10

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

22

Hint

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$.

Therefore, $\sum\limits_{i=1}^3 \sum\limits_{j=1}^3 f(i,j)=10$.

Constraints

This problem enables subtask bundling and subtask dependencies.

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

Special property $A$: Node $1$ is fixed as the root of the tree. For any pair of nodes $(x,y)$ with $x \neq y$, if $x$ is an ancestor of $y$, then $t_x < t_y$.

Special property $B$: $\forall i\in[1,n), a_i=i, b_i=i+1$.

Translated by ChatGPT 5