Problem1094--不堪重负的树

1094: 不堪重负的树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 40  Solved: 25
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI非常喜欢树,然后他生成了一个大森林给自己玩。
玩着玩着,PIPI陷入了沉思。
一棵树由N个节点组成,编号为i的节点有一个价值Wi。
假设从树根出发前往第i个节点(可能是树根自己),一共需要经过Di个节点(包括起点和终点),那么这个节点对这棵树产生的负担就是Di与Wi的乘积。
对于一棵树而言,这棵树的负担值为所有节点对它产生的负担之和。
PIPI学习了dfs,如果他知道树的结构,他当然可以很容易地算出树的负担值。可是现在沉思中的PIPI并不知道树的结构形态,他只知道一棵二叉树的中序遍历以及每个节点的价值,那么这棵二叉树可能的最小负担值是多少呢?

Input

多组数据
每组数据包括三行。
第一行为一个正整数N(N≤200)。
第二行为N个正整数Wi(Wi≤100000000),表示编号为i的节点的价值。
第三行为N个正整数Pi(Pi≤N),为一个1~N的排列,表示二叉树的中序遍历结果。

Output

对于每组数据,输出一行一个正整数,表示这棵树可能的最小负担值。

Sample Input

4
1 2 3 4
1 2 3 4
7
1 1 1 1 1 1 1
4 2 3 5 7 1 6

Sample Output

18
17

Source/Category