题解
神仙dp啊QAQ
我们发现我们需要枚举一个起点，遍历完它所有的儿子然后向上爬
设\(f[i][j]\)表示第i个点的子树全部处理完之后到达i深度为j的祖先的兄弟处
我们只需要对叶子节点和只有一个儿子的点特殊讨论，因为所有的向上爬都是从叶子爬的
转移的时候只要枚举从两个儿子里哪个爬上取就好了
设\(g[i][j]\)表示第i个点的子树全部处理完之后到达i深度为j的祖先处
转移个f数组类似，但是要用到f数组
枚举每个点当起点的时候，遵循x的父亲->x的兄弟->x的父亲的父亲->x的父亲的兄弟这样顺序来覆盖即可
代码
#include <bits/stdc++.h>
//#define ivorysi
#define enter putchar('\n')
#define space putchar(' ')
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define mo 974711
#define MAXN 200005
#define pii pair<int,int>
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,dep[MAXN];
int64 a[MAXN],b[MAXN],dis[MAXN],f[MAXN][18],g[MAXN][18];
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) read(a[i]);
for(int i = 2 ; i <= N ; ++i) read(b[i]);
for(int i = 1 ; i <= N ; ++i) {
dep[i] = dep[i >> 1] + 1;
dis[i] = dis[i >> 1] + b[i];
}
for(int u = N ; u >= 1 ; --u) {
if((u << 1) > N) {
for(int j = dep[u]; j >= 2 ; --j) {
int fa = u >> (dep[u] - j + 1),x = (u >> (dep[u] - j)) ^ 1;
f[u][j] = (dis[u] + dis[x] - 2 * dis[fa]) * a[x];
}
}
else if((u << 1) == N) {
for(int j = dep[u] ; j >= 2 ; --j) {
f[u][j] = f[u << 1][j] + a[u << 1] * b[u << 1];
}
}
else {
int lc = u << 1,rc = u << 1 | 1;
for(int j = dep[u] ; j >= 2 ; --j) {
f[u][j] = min(a[lc] * b[lc] + f[lc][dep[lc]] + f[rc][j],a[rc] * b[rc] + f[rc][dep[rc]] + f[lc][j]);
}
}
}
for(int u = N ; u >= 1 ; --u) {
if((u << 1) > N) {
for(int j = dep[u] - 1; j >= 0 ; --j) {
int fa = u >> (dep[u] - j);
g[u][j] = (dis[u] - dis[fa]) * a[fa];
}
}
else if((u << 1) == N) {
for(int j = dep[u] - 1 ; j >= 0 ; --j) {
g[u][j] = g[u << 1][j] + a[u << 1] * b[u << 1];
}
}
else {
int lc = u << 1,rc = u << 1 | 1;
for(int j = dep[u] - 1 ; j >= 0 ; --j) {
g[u][j] = min(a[lc] * b[lc] + f[lc][dep[lc]] + g[rc][j],a[rc] * b[rc] + f[rc][dep[rc]] + g[lc][j]);
}
}
}
int64 ans = 1e18;
for(int u = N ; u >= 1 ; --u) {
int64 res = g[u][dep[u] - 1];
for(int x = u ; x > 1 ; x >>= 1) {
int t = x ^ 1;
if(t > N) res += a[x >> 2] * b[x >> 1];
else res += a[t] * b[t] + g[t][dep[t] - 2];
}
ans = min(ans,res);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}