bzoj#P4446. [SCOI2015] 小凸玩密室

[SCOI2015] 小凸玩密室

题目描述

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

输入格式

11 行包含 11 个数 nn,代表节点的个数

22 行包含 nn 个数,代表每个节点的权值 aia_i(i=1,2,(i = 1, 2,……,n), n)

33 行包含 n1n - 1 个数,代表每条边的权值 bib_i,第 ii 号边是由第 (i+1)/2(i+1)/2 号点连向第 i+1i + 1 号点的边。(i=1,2,(i = 1, 2,……,n1), n - 1)

输出格式

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

3
5 1 2
2 1
5

提示

  • 对于 1010% 的数据, 1n101 \leq n \leq 10
  • 对于 2020% 的数据, 1n201 \leq n \leq 20
  • 对于 3030% 的数据, 1n20001 \leq n \leq 2000
  • 对于 100100% 的数据, 1n2105,1ai,bi1051 \leq n \leq 2 * 10^5, 1 \leq a_i, b_i \leq 10^5