#2009. 「SCOI2015」小凸玩密室

内存限制：256 MiB时间限制：1000 ms标准输入输出

题目类型：传统评测方式：文本比较

上传者：匿名

提交提交记录统计讨论测试数据

题目描述

小凸和小方相约玩密室逃脱，这个密室是一棵有 n nn 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 Ai A_iAi，每条边也有个权值 bi b_ibi。

点亮第 1 11 个灯泡不需要花费，之后每点亮一个新的灯泡 V VV 的花费，等于上一个被点亮的灯泡 U UU 到这个点 V VV 的距离 D(u,v) D(u, v)D(u,v)，乘以这个点的权值 Av A_vAv。

在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。

输入格式

第一行包含一个数 n nn，代表节点的个数。
第二行包含 n nn 个数，代表每个节点的权值 ai a_iai。
第三行包含 n−1 n - 1n−1 个数，代表每条边的权值 bi b_ibi，第 i ii 号边是由第 i+12 \frac{i + 1}{2}2i+1 号点连向第 i+1 i + 1i+1 号点的边。

输出格式

输出包含一个数，代表最少的花费。

样例

样例输入

样例输出

数据范围与提示

1≤N≤2×105,1<Ai,Bi≤105 1 \leq N \leq 2 \times 10 ^ 5, 1 < A_i, B_i \leq 10 ^ 51≤N≤2×105,1<Ai,Bi≤105

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=,M=;

typedef long long LL;

int n;

LL a[N],b[N],dep[N],dis[N];

LL f[N][M],g[N][M],ans;

char c;

int read()

{

    for (c=getchar();c<'' || c>'';c=getchar());

    int x=c-;

        for (c=getchar();c>='' && c<='';c=getchar()) x=x*+c-;

        return x;

}

int main(){

    n=read();

        for (int i=;i<=n;i++) a[i]=read();

        dep[]=;

        for (int i=;i<=n;i++){

            b[i]=read();

            dep[i]=dep[i>>]+; dis[i]=dis[i>>]+b[i];

        }

        for (int i=n;i;i--){

            for (int j=;j<dep[i];j++){

                int lca=(i>>(dep[i]-j)),x=(i>>(dep[i]-j-))^,lt=i<<;

                    if (lt>n) f[i][j]=(LL)a[x]*(dis[i]+dis[x]-dis[lca]*);

                    else if (lt==n) f[i][j]=(LL)a[lt]*b[lt]+f[lt][j];

                    else f[i][j]=min((LL)a[lt]*b[lt]+f[lt][dep[i]]+f[lt|][j],(LL)a[lt|]*b[lt|]+f[lt|][dep[i]]+f[lt][j]);

            }

        }

        for (int i=n;i;i--){

            for (int j=;j<dep[i];j++){

                int x=i>>(dep[i]-j),lt=i<<;

                    if (lt>n) g[i][j]=(LL)a[x]*(dis[i]-dis[x]);

                    else if (lt==n) g[i][j]=(LL)a[lt]*b[lt]+g[lt][j];

                    else g[i][j]=min((LL)a[lt]*b[lt]+f[lt][dep[i]]+g[lt|][j],(LL)a[lt|]*b[lt|]+f[lt|][dep[i]]+g[lt][j]);

            }

        }

        ans=g[][];

        for (int i=;i<=n;i++){

            LL s=g[i][dep[i]-];

            for (int j=i;j>;j>>=){

                int x=j^,y=j>>;

                    if (x>n) s+=(LL)a[y>>]*b[y];

                    else s+=(LL)a[x]*b[x]+g[x][dep[y]-];

            }

            if (s<ans) ans=s;

        }

        printf("%lld\n",ans);

        return ;

}

巴特西

—Libre#2009. 「SCOI2015」小凸玩密室