P10795 『SpOI - R1』Lamborghini (Demo)

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

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 one line with one integer, the answer.

#### 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$. | Subtask | $n\leq$ | $t_i,v_i\leq$ | Special Property | Score | Dependencies | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | 1 | $300$ | $10^5$ | None | $15$ | None | | 2 | $5000$ | $10^5$ | None | $15$ | 1 | | 3 | $10^5$ | $10^9$ | $A$ | $15$ | None | | 4 | $10^5$ | $10^9$ | $B$ | $15$ | None | | 5 | $10^5$ | $10^9$ | None | $40$ | 1,2,3,4 | 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