AT_arc228_b.Minimize Topological Order

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ and a length-$N$ sequence of positive integers $A=(A_1,A_2,\dots,A_N)$.

For a rooted tree $T$ with $N$ vertices numbered $1$ through $N$, define $f(T)$ as follows.

Among the permutations $Q=(Q_1,Q_2,\dots,Q_N)$ of $(1,2,\dots,N)$, call one that satisfies the following condition a good permutation.

• For every vertex $v$ other than the root, letting $u$ be its parent, $u$ appears before $v$ in $Q$.

Let $f(T)$ be the lexicographically smallest good permutation.

Also, define the cost of a rooted tree $T$ with $N$ vertices as $\sum_{i=1}^{N} A_i c_i^2$, where $c_i$ is the number of children of vertex $i$ in $T$.

Find the minimum cost of a rooted tree $T$ with $N$ vertices satisfying $f(T) = P$.

给你一个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$ 和一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。

对于一棵以 $1$ 至 $N$ 编号的 $N$ 个顶点构成的有根树 $T$，定义 $f(T)$ 如下：

在所有 $(1,2,\dots,N)$ 的排列 $Q=(Q_1,Q_2,\dots,Q_N)$ 中，称满足如下条件的排列为好排列：

• 对于除根以外的每个顶点 $v$，设其父节点为 $u$，则 $u$ 在 $Q$ 中出现在 $v$ 之前。

定义 $f(T)$ 为字典序最小的好排列。

此外，定义一棵含 $N$ 个顶点的有根树 $T$ 的代价为 $\sum_{i=1}^{N} A_i c_i^2$，其中 $c_i$ 表示顶点 $i$ 在 $T$ 中的子节点数目。

求满足 $f(T) = P$ 的、含 $N$ 个顶点的有根树 $T$ 的最小代价。

The input is given from Standard Input in the following format:

$N$
$P_1\ P_2\ \dots\ P_N$
$A_1\ A_2\ \dots\ A_N$

输入从标准输入中按以下格式给出：

$N$
$P_1\ P_2\ \dots\ P_N$
$A_1\ A_2\ \dots\ A_N$

Output the answer.

输出答案。

Sample 1 Explanation:
The trees satisfying the condition for $T$ are the following two trees, $T_1$ and $T_2$, both rooted at vertex $1$.

The cost of $T_1$ is $1 \times 2^2 + 2 \times 0^2 + 1 \times 0^2 = 4$, and the cost of $T_2$ is $1 \times 1^2 + 2 \times 1^2 + 1 \times 0^2 = 3$, so the minimum cost is $3$.

Constraints

• $1 \le N \le 2 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• $1 \le A_i \le 10^6$
• All input values are integers.

样例 1 解释：
满足条件的树 $T$ 有以下两棵，即以顶点 $1$ 为根的树 $T_1$ 和 $T_2$。

$T_1$ 的代价为 $1 \times 2^2 + 2 \times 0^2 + 1 \times 0^2 = 4$，
$T_2$ 的代价为 $1 \times 1^2 + 2 \times 1^2 + 1 \times 0^2 = 3$，
因此最小代价为 $3$。

约束条件

• $1 \le N \le 2 \times 10^5$
• $P$ 是 $(1,2,\dots,N)$ 的一个排列。
• $1 \le A_i \le 10^6$
• 所有输入值均为整数。