/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
(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 に対して、v の親を頂点 u とした時、Q において u は v より前に現れる。
良い順列のうち、辞書順最小のものを f(T) とする。
また、N 頂点の根付き木 T のコストを \sum_{i=1}^{N} A_i c_i^2 と定義します。ここで、c_i は T における頂点 i の子の個数です。
N 頂点の根付き木 T のうち f(T) = P を満たすものに対する T のコストの最小値を求めてください。
制約
- 1 \le N \le 2 \times 10^5
- P は (1,2,\dots,N) の順列
- 1 \le A_i \le 10^6
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1\ P_2\ \dots\ P_N A_1\ A_2\ \dots\ A_N
出力
答えを出力せよ。
入力例 1
3 1 2 3 1 2 1
出力例 1
3
T として条件を満たすのは、頂点 1 を根とした木のうち以下の T_1,T_2 の 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 です。
入力例 2
5 3 1 5 2 4 4 1 1 2 1
出力例 2
6
入力例 3
10 8 4 7 9 1 3 2 10 6 5 816977 838423 186050 232610 582528 327642 432740 420943 194307 966417
出力例 3
3901780
Score : 800 points
Problem Statement
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.
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.
Input
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
Output the answer.
Sample Input 1
3 1 2 3 1 2 1
Sample Output 1
3
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.
Sample Input 2
5 3 1 5 2 4 4 1 1 2 1
Sample Output 2
6
Sample Input 3
10 8 4 7 9 1 3 2 10 6 5 816977 838423 186050 232610 582528 327642 432740 420943 194307 966417
Sample Output 3
3901780