题目描述
小凸和小方相约玩密室逃脱，这个密室是一棵有
n
n
n 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值
A
i
A_i
Ai，每条边也有个权值
b
i
b_i
bi。
点亮第
1
1
1 个灯泡不需要花费，之后每点亮一个新的灯泡
V
V
V 的花费，等于上一个被点亮的灯泡
U
U
U 到这个点
V
V
V 的距离
D
(
u
,
v
)
D(u, v)
D(u,v)，乘以这个点的权值
A
v
A_v
Av。
在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。
数据范围
1
≤
N
≤
2
×
1
0
5
,
1
<
A
i
,
B
i
≤
1
0
5
1 \leq N \leq 2 \times 10 ^ 5, 1 < A_i, B_i \leq 10 ^ 5
1≤N≤2×105,1<Ai,Bi≤105
题解
考虑暴力，
f
i
,
j
f_{i,j}
fi,j 表示走完
i
i
i 子树，直接走到
j
j
j 的最小花费，转移考虑用左右儿子转移。
可以发现我们只需要知道
j
j
j 为
i
i
i 的祖先或者祖先的另一个儿子的
f
f
f 值即可，于是复杂度降至
n
l
o
g
n
nlogn
nlogn 。
注意
i
i
i 为叶子或者
i
i
i 只有左儿子的情况。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std
;
const int N
=2e5+5;
int n
;LL a
[N
],b
[N
],f
[N
][20],g
[N
][20],ans
=2e18;
int main(){
scanf("%d",&n
);
for (int i
=1;i
<=n
;i
++)
scanf("%lld",&a
[i
]);
for (int i
=2;i
<=n
;i
++)
scanf("%lld",&b
[i
]),b
[i
]+=b
[i
>>1];
for (int i
=n
,l
,r
;i
;i
--){
l
=i
<<1;r
=l
|1;
for (int j
=i
,x
,y
=1;j
>1;j
>>=1,y
++){
x
=j
^1;
if (l
>n
) f
[i
][y
]=a
[x
]*(b
[i
]+b
[x
]-(b
[j
>>1]<<1));
else if (r
>n
) f
[i
][y
]=f
[l
][y
+1]+a
[l
]*(b
[l
]-b
[i
]);
else f
[i
][y
]=min(a
[l
]*(b
[l
]-b
[i
])+f
[l
][1]+f
[r
][y
+1],
a
[r
]*(b
[r
]-b
[i
])+f
[r
][1]+f
[l
][y
+1]);
}
}
for (int i
=n
,l
,r
;i
;i
--){
l
=i
<<1;r
=l
|1;
for (int j
=i
>>1,y
=1;;j
>>=1,y
++){
if (l
>n
) g
[i
][y
]=a
[j
]*(b
[i
]-b
[j
]);
else if (r
>n
) g
[i
][y
]=g
[l
][y
+1]+a
[l
]*(b
[l
]-b
[i
]);
else g
[i
][y
]=min(a
[l
]*(b
[l
]-b
[i
])+f
[l
][1]+g
[r
][y
+1],
a
[r
]*(b
[r
]-b
[i
])+f
[r
][1]+g
[l
][y
+1]);
if (!j
) break;
}
}
for (int j
,x
,i
=1;i
<=n
;i
++){
LL v
=g
[i
][1];j
=i
>>1;x
=i
^1;
while(j
){
if (x
>n
) v
+=a
[j
>>1]*(b
[j
]-b
[j
>>1]);
else v
+=a
[x
]*(b
[x
]-b
[j
])+g
[x
][2];
x
=j
^1;j
>>=1;
}
ans
=min(ans
,v
);
}
return cout
<<ans
<<endl
,0;
}
