AT_arc228_b [ARC228B] 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 $ .

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 $

Output the answer.

### Sample Explanation 1 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.