『SpOI - R1』Lamborghini (Demo)

给你一棵无根树，每个点 $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$。 | Subtask | $n\leq$ | $t_i,v_i\leq$ | 特殊性质 | 得分 | 子任务依赖 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | 1 | $300$ | $10^5$ | 无 | $15$ | 无 | | 2 | $5000$ | $10^5$ | 无 | $15$ | 1 | | 3 | $10^5$ | $10^9$ | $A$ | $15$ | 无 | | 4 | $10^5$ | $10^9$ | $B$ | $15$ | 无 | | 5 | $10^5$ | $10^9$ | 无 | $40$ | 1,2,3,4 | 特殊性质 $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$。