用ui,j表示走完i的子树后走到i的深度为j的祖先的兄弟的最小代价;
用vi,j表示走完i的子树后走到i的深度为j的祖先的最小代价,用u算出v。
枚举起点,计算答案。
#include<algorithm>
#include<cstdio>
using std::min;
typedef long long ll;
const int N=2e5+5;
ll a[N],b[N],c[N],f[N][19][2];
int main(){
struct{
operator int(){
int x=0,c=getchar();
while(c<48)c=getchar();
while(c>47)
x=x*10+c-48,c=getchar();
return x;
}
}it;
int n=it;
for(int i=1;i<=n;++i)
a[i]=it;
for(int i=2;i<=n;++i){
b[i]=it;
c[i]=c[i>>1]+b[i];
}
for(int i=n;i;--i)
for(int j=1;i>>j-1;++j)
if(i<<1>n){
f[i][j][0]=(c[i]-c[i>>j]+b[i>>j-1^1])*a[i>>j-1^1];
f[i][j][1]=(c[i]-c[i>>j])*a[i>>j];
}else{
f[i][j][0]=i<<1<n?min(b[i<<1]*a[i<<1]+f[i<<1][1][0]+f[i<<1^1][j+1][0],b[i<<1^1]*a[i<<1^1]+f[i<<1^1][1][0]+f[i<<1][j+1][0]):b[i<<1]*a[i<<1]+f[i<<1][j+1][0];
f[i][j][1]=i<<1<n?min(b[i<<1]*a[i<<1]+f[i<<1][1][0]+f[i<<1^1][j+1][1],b[i<<1^1]*a[i<<1^1]+f[i<<1^1][1][0]+f[i<<1][j+1][1]):b[i<<1]*a[i<<1]+f[i<<1][j+1][1];
}
if(~n&1)
f[n^1][2][1]=b[n>>1]*a[n>>2];
ll z=1e18;
for(int i=n;i;--i){
ll s=f[i][1][1];
for(int j=i;j>>1;j>>=1)
s+=b[j^1]*a[j^1]+f[j^1][2][1];
z=min(z,s);
}
printf("%lld\n",z);
}