F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 4446. -- [Scoi2015]小凸玩密室

4446: [Scoi2015]小凸玩密室

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 529  Solved: 227
[Submit][Status][Discuss]

Description

小凸和小方相约玩密室逃脱,这个密室是一棵有n个节点的完全二叉树,每个节点有一个灯泡。点亮所有灯泡即可
逃出密室。每个灯泡有个权值Ai,每条边也有个权值bi。点亮第1个灯泡不需要花费,之后每点亮1个新的灯泡V的
花费,等于上一个被点亮的灯泡U到这个点V的距离Du,v,乘以这个点的权值Av。在点灯的过程中,要保证任意时刻
所有被点亮的灯泡必须连通,在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。
请告诉他们,逃出密室的最少花费是多少。

Input

第1行包含1个数n,代表节点的个数
第2行包含n个数,代表每个节点的权值ai。(i=l,2,…,n)
第3行包含n-l个数,代表每条边的权值bi,第i号边是由第(i+1)/2号点连向第i+l号点的边。
(i=l,2...N-1)

Output

输出包含1个数,代表最少的花费。

Sample Input

3
5 1 2
2 1

Sample Output

5

HINT

对于100%的数据,1≤N≤2×105,1<Ai,Bi≤10^5


Source

[Submit][Status][Discuss]

HOME Back