洛谷P4253 [SCOI2015]小凸玩密室题解

题目链接：P4253 [SCOI2015]小凸玩密室

题意：

小凸和小方相约玩密室逃脱。

这个密室是一棵有 $n$ 个节点的完全二叉树，每个节点有一个灯泡，点亮所有灯泡即可逃出密室。

每个灯泡有个权值 $a_i$，每条边也有个权值 $b_i$。

点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 $v$ 的花费，等于上一个被点亮的灯泡 $u$ 到这个点 $v$ 的距离 $D_{u,v}$，乘以这个点的权值 $a_v$ 。

在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。

请告诉他们，逃出密室的最少花费是多少。

输入格式：

第 $1$ 行包含 $1$ 个数 $n$，代表节点的个数

第 $2$ 行包含 $n$ 个数，代表每个节点的权值 $a_i$。 $(i = 1, 2,$……$, n)$

第 $3$ 行包含 $n - 1$ 个数，代表每条边的权值 $b_i$，第 $i$ 号边是由第 $\left\lfloor\frac{(i+1)}{2}\right\rfloor$ 号点连向第 $i + 1$ 号点的边。$(i = 1, 2,\cdots, n - 1)$

输出格式：

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

数据范围：

对于 $100$% 的数据， $1 \leq n \leq 2 \times 10^5, 1 \leq a_i, b_i \leq 10^5$

欠了~~几百年~~的作业。。。趁这几天停课准备初赛赶紧写了它。

注意题目给出的是完全二叉树，这意味着树高为 $\Theta(\log n)$

由于「任意时刻点亮的灯泡都必须连通」，且「点亮一个灯泡后必须点亮其子树」

那么这个点灯泡的过程就是

点亮某个灯泡 $u$
按某种顺序点亮它的某个子树
回到 $\mathtt{fa}$ ，并进行类似的操作

设 $f_{i,j}$ 表示点亮 $i$ 后回到 $i$ 的第 $j$ 个祖先的最小花费（不是 $2^j$ 个祖先哦）

设 $g_{i,j}$ 表示点亮 $i$ 后回到 $i$ 的第 $j$ 个祖先的另一个儿子的最小花费。

然后就是极其毒瘤的代码了。采用了非递归的写法。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+5))

const int mx = 18;
int n,ans=INF,ls[N],rs[N],val[N],f[N][20],g[N][20],dis[N][20];
// k 的第 x 个祖先的另一个儿子
#define bo(k,x) ((k >> (x-1)) ^ 1)
int solve()
{
    for(int k=n; k>=1; k--) // 自底向上枚举每个结点
    {
        if(!ls[k]) // 叶子结点
        {
            for(int i=1; k>>(i-1); i++)
                g[k][i] = (dis[k][i] + dis[bo(k,i)][1]) * val[bo(k,i)];
        }else if(!rs[k]) // 只有左儿子
        {
            for(int i=1; k>>(i-1); i++)
                g[k][i] = dis[ls[k]][1] * val[ls[k]] + g[ls[k]][i+1];
        }else // 两个儿子，则选一个顺序使得花费最小
        {
            for(int i=1; k>>(i-1); i++)
                g[k][i] = min( dis[ls[k]][1] * val[ls[k]] + g[ls[k]][1] + g[rs[k]][i+1],
                    dis[rs[k]][1] * val[rs[k]] + g[rs[k]][1] + g[ls[k]][i+1] );
        }
    }
    for(int k=n; k>=1; k--)
    {
        if(!ls[k])
        {
            for(int i=1; k>>(i-1); i++)
                f[k][i] = dis[k][i] * val[k>>i];
        }else if(!rs[k])
        {
            for(int i=1; k>>(i-1); i++)
                f[k][i] = f[ls[k]][i+1] + dis[ls[k]][1] * val[ls[k]];
        }else
        {
            for(int i=1; k>>(i-1); i++)
                f[k][i]=min( dis[ls[k]][1] * val[ls[k]] + g[ls[k]][1] + f[rs[k]][i+1],
                    dis[rs[k]][1] * val[rs[k]] + g[rs[k]][1] + f[ls[k]][i+1] );
        }
    }
    for(int k=1; k<=n; k++) // 依次考虑每个结点作为起点
    {
        int sum = f[k][1];
        for(int i=1, fa=k>>1; fa; ++i, fa>>=1)
        {
            int bro = bo(k,i);
            if(bro > n) sum += dis[fa][1] * val[fa >> 1];
            else sum += dis[bro][1] * val[bro] + f[bro][2];
        }
        down(ans, sum);
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=2; i<=n; i++) cin >> dis[i][1];
    for(int i=1; i<= (n >> 1) + 1; i++)
    {
        if((i << 1) <= n) ls[i] = (i << 1); else break;
        if((i << 1 | 1) <= n) rs[i] = (i << 1 | 1);
    }
    for(int i=2; i<=mx; i++)
        for(int k=n; k>>i; k--)
            dis[k][i] = dis[k][i-1] + dis[k >> (i-1)][1];
    cout << solve() << '\n';
    return 0;
}