题目描述

给你一棵无根树，每个点 $i$ 有两个属性 $t_i,v_i$。

定义有向路径 $i\to j$ 的 $f_{i,j}$ 为：

• 若 $i\to j$ 上 $t_x$ 最小的点为 $x$ 且 $v_j\leq v_x\leq v_i$，则 $f_{i,j}=x$。
• 否则，$f_{i,j}=0$。

求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{i,j}$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个以空格分隔的整数，第 $i$ 项表示点 $i$ 的 $t_i$。

第三行 $n$ 个以空格分隔的整数，第 $i$ 项表示点 $i$ 的 $v_i$。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示一条树边 $a\leftrightarrow b$。

输出格式

输出一行一个整数，表示答案。

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

提示

样例 #1 解释

• $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$。

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

数据范围

本题开启子任务捆绑与子任务依赖。

对于 $100\%$ 的数据，$t$ 互不相同，$1\leq n\leq 10^5$，$1\leq t_i,v_i\leq 10^9$。

特殊性质 $A$：钦定 $1$ 号节点为树的根，对于任意点对 $(x,y)$ 且 $x\neq y$，若 $x$ 是 $y$ 的祖先，则 $t_x<t_y$。

特殊性质 $B$：$\forall i\in[1,n),a_i=i,b_i=i+1$。