这道题实在太苟了。

因为不知道$dist(u,v)$的$u$从子树的哪个位置来,但确定一定是某一个叶子节点

还要处理是哪个子树先进行,好烦啊。。。

那就预处理一下叶子结点吧,有状态$f_{i,j,0}$表示从$i$号叶子结点返回到它的第$j$个祖先(未点灯)的费用。

这个不难处理$f_{i,j,0}=dist(i,p_{i,j})*a_{p_{i,j}}$

从一个子树中出来,进到另一个子树的情况把它简化成两个叶子结点之间的转移。

有$f_{i,j,1}$表示从$i$号叶子结点返回到它的第$j$个祖先(未点灯)的另一个儿子的费用

这个也不难,所以不写了。

好了,现在有两棵子树$ls,rs$,根节点$i$。

根据$DP$的思想,现在已经处理好了$ls,rs$的状态。

如果根节点要返回到第$j$个祖先,那么返回的起点就一定来自于左子树,或者右子树的某一个叶子结点。

根据之前的预处理,就可以联想到根节点的状态如何定义与转移。

$f_{i,j,0}$表示已经处理好了以$i$为根的子树,且返回到它的第$j$个祖先的费用

$f_{i,j,1}$同理,具体方程见代码。

但是

这道题还有一个坑点,并没确定哪个是第一个点亮的。

所以还需要进行一些操作。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e5+5,mod=20170408;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[N][19][2],d[N][19],b[N],a[N];int Log[N];int n;
void dp()
{
    for(int i=n;i;i--)
        for(int j=1;j<=Log[i];j++)
        {
            int w=(i>>(j-1))^1;
            if((i<<1)>n)
            {
                f[i][j][0]=d[i][j]*a[i>>j];
                f[i][j][1]=(d[i][j]+d[w][1])*a[w];
            }
            else if(((i<<1)|1)>n)
            {
                int ls=i<<1;
                f[i][j][0]=f[ls][j+1][0]+d[ls][1]*a[ls];
                f[i][j][1]=f[ls][j+1][1]+d[ls][1]*a[ls];//要下去到ls,也要算上。 
            }
            else
            {
                int ls=i<<1,rs=i<<1|1;
                f[i][j][0]=min(f[ls][j+1][0]+f[rs][1][1]+d[rs][1]*a[rs],f[rs][j+1][0]+f[ls][1][1]+d[ls][1]*a[ls]);
                f[i][j][1]=min(f[ls][j+1][1]+f[rs][1][1]+d[rs][1]*a[rs],f[rs][j+1][1]+f[ls][1][1]+d[ls][1]*a[ls]);
            }
        }
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        ll tmp=f[i][1][0];int t=1;
        for(int x=i>>1,lst=i;t<=Log[i];lst=x,x=x>>1)
        {
            int w=lst^1;++t;
            if(w<=n)tmp+=d[w][1]*a[w]+f[w][2][0];//如果有,那就继承。 
            else tmp+=d[x][1]*a[x>>1];//如果没有,让x上去,因为x是最后点亮那个 
        }
        ans=min(tmp,ans);
    }
    qw(ans);puts("");
}
int main()
{
    qr(n);
    for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;i++)qr(a[i]);
    for(int i=2;i<=n;i++)qr(b[i]);
    for(int i=2;i<=n;i++)
        for(int j=1;j<Log[i];j++)
            d[i][j]=d[i>>1][j-1]+b[i];
    dp();
    return 0;
}