A5975. 「SCOI2015」小凸玩密室
编程题
省选/NOI-
知识点
题目描述
小凸和小方相约玩密室逃脱，这个密室是一棵有 $n$ 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 $A_i$，每条边也有个权值 $b_i$。
点亮第 $1$ 个灯泡不需要花费，之后每点亮一个新的灯泡 $V$ 的花费，等于上一个被点亮的灯泡 $U$ 到这个点 $V$ 的距离 $D(u, v)$，乘以这个点的权值 $A_v$。
在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。
点亮第 $1$ 个灯泡不需要花费，之后每点亮一个新的灯泡 $V$ 的花费，等于上一个被点亮的灯泡 $U$ 到这个点 $V$ 的距离 $D(u, v)$，乘以这个点的权值 $A_v$。
在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。
输入格式
第一行包含一个数 $n$，代表节点的个数。
第二行包含 $n$ 个数，代表每个节点的权值 $a_i$。
第三行包含 $n - 1$ 个数，代表每条边的权值 $b_i$，第 $i$ 号边是由第 $\frac{i + 1}{2}$ 号点连向第 $i + 1$ 号点的边。
第二行包含 $n$ 个数，代表每个节点的权值 $a_i$。
第三行包含 $n - 1$ 个数，代表每条边的权值 $b_i$，第 $i$ 号边是由第 $\frac{i + 1}{2}$ 号点连向第 $i + 1$ 号点的边。
输出格式
输出包含一个数，代表最少的花费。
输入输出样例
输入 #1
3 5 1 2 2 1
输出 #1
5
说明/提示
$1 \leq N \leq 2 \times 10 ^ 5, 1 < A_i, B_i \leq 10 ^ 5$