自动搬运

查看原文

来自洛谷，原作者为

	Mihari 您也是这样吧，因为战斗到底——因为努力求生，现在，才能站在这里。

搬运于2025-08-24 21:58:12，当前版本为作者最后更新于2019-11-14 14:33:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

T 「SCOI2015」小凸玩密室

题目

点这里

考场思路

题目读错了，导致我暴力都打不出来...

其实题目要求的是一定要将某一棵子树全部扫完再去扫其他的子树。

而不是左边扫一下，右边扫一下...

正解

首先，这里补充一个数据范围 （考试的时候也有）

---

对于 $10\%$ 的数据，$1≤n≤10$；

另有 $10\%$ 的数据， $1≤n≤20$ ；

另有 $10\%$ 的数据， $1≤n≤2000$ ；

另有 $20\%$ 的数据， $1≤n≤20000$ ；

对于 $100\%$ 的数据， $1≤n≤2\times 10^5$ ， $1≤A_i≤10^5$ ， $1≤B_i≤10^5$ 。

---

再次引用这句话 虽然是我自己编的

所谓信息竞赛，其实就是面向数据编程

其实，根据数据范围，一步一步想出算法并优化其实也是一个解题的好方法。

---

子方案 1 (10pts)

首先，看前 $10\%$ 的数据，这个地方我们可以怎么做呢？

这样的暴力其实很简单，用 $O(n!)$ 枚举我们访问的顺序。

再判断这个顺序是否合法，最后计算花费即可。

---

子方案 2 (20pts)

但是很明显，对于 $10pts$ 的算法，是过不了第二个 $10pts$ 的数据点的。

怎么进行优化？

注意到子方案 $1$ 中有这样的操作：

随意枚举顺序，再判断是否合法。

这样做让我们用很多时间枚举了很多不合法的访问顺序。

那么我们是否可以让我们枚举的序列本来就合法，只需直接去算花费？

这是肯定可以的，时间复杂度 $O(2^n)$，因为我们要分左、右儿子去构造访问顺序。

这样，时间复杂度应该是 $O(n2^n\cdot nlog^n_2)$。

---

子方案 3 (50pts)

对于子方案 $2$ 的优化显然是很好的，但是这都基于 暴力 这一思想，接下来我们需要转换思路。

考虑我们是怎么点亮一个子树的。

对于一个子树，它的根是 $u$，左儿子是 $lc$，右儿子是 $rc$。

假若我们先访问左子树，先不管它是怎么访问的。

那么，我们在左子树里面的访问顺序是否对后面的状态有影响？

是有的，证明如下： 本人数学不好，没有严格数学书写顺序

假设我们在左子树里面的访问顺序中的某一种是以 $x$ 结尾。

很显然这个 $x$ 有很多个。

而当我们从左子树到右子树去的时候，先要访问右子树的树根，即 $rc$。

那么这个花费显然是 $dis(x,rc)*A[rc]$。

而又因为这个 $x$ 有很多个，那么很显然。不同的 $x$ 是会有不同的花费。

因而左子树里面的访问顺序是对后面的状态有影响。

而且很显然，对后面状态有影响的只有最后访问的那个点在哪里。

所以，我们就可以定义状态 $f[u][x]$ 为访问完以 $u$ 为根的子树（不包含 $u$）且结尾在 $x$ 时的最小花费。

那么，就可以分类进行状转：

• 当 $x$ 在左子树上时，$f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\}$
• 当 $x$ 在右子树上时，$f[u][y]=min\{dis(u,rc)\times A[rc]+f[rc][x]+dis(x,lc)\times A[lc]+f[lc][y]\}$

很显然，状转中 $x、y$ 都是需要循环枚举的，因而这个状转大概是 $O(n^2)$ 的复杂度。

所以总复杂度是 $O(n^3)$。

但其实这样的计算是不准确的，准确复杂度应该是 $\sum\frac{n^2}{2^{x+2}}$。

这个复杂度是通过分层计算得出。

不难看出，这个复杂度可得到 $50pts$ 的高分。

---

子方法 4 (正解)

我们发现，对于子方法三，其实已经快要过掉这道题了。

但是哪里的时间复杂度较高呢？

毋庸置疑的，状转的 $O(n^2)$ 其实已经非常高了。

怎么减下来？肯定是要针对其状转简化。

观察状转：

• 当 $x$ 在左子树上时，$f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\}$
• 当 $x$ 在右子树上时，$f[u][y]=min\{dis(u,rc)\times A[rc]+f[rc][x]+dis(x,lc)\times A[lc]+f[lc][y]\}$

我们先考虑其中一个状转，另一个其实是对应的。

拿第一个算式来说

$$f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\} $$

考虑将其分解：

对于 $dis(x,rc)$ ，其实不难看出

$$dis(x,rx)=dis(x,u)+dis(u,rc)$$

而这里面，只有 $dis(x,u)$ 是改变的。

那么我们只需将 $dis(x,u)$ 也存入状态中，就可以同时考虑它的最小值了。

所以，访问一边的最小花费就是

$$ans2=f[lc][x]+dis(u,rc)\times A[rc]+[dis(u,x)+dis(u,rc)]\times A[rc] $$

最后的花费，就是 $ans2+f[lc][x]$ 了。

最后，根据这个 $x$ 到底在左边还是在右边进行分类转移即可。

但是，这就是最后的答案了吗？

肯定不是，题目并未要求我们必须从 $1$ 开始。

所以，定义另一个状态 $t[i][j]$：访问完 $i$ 的子树，结尾在 $j$ 时的最小花费。

那么这个怎么转移呢？

这里可以自行思考了

如果还是想不出来，看看代码吧，看看代码总有好处的

std version

#include<bits/stdc++.h>
#define mz 1000000007
using namespace std;

long long inf=mz*1LL*mz;
long long dep[200005];
int n,a[200005],b[200005];
vector <long long> dp[200005],dis[200005],dpp[200005];

void dfs(int x)
{
    dep[x]=dep[x/2]+b[x];//计算伪深度, 方便计算距离
    if(x*2<=n)//有左儿子
    {
        dfs(x*2);//先访问左儿子
        int t=dp[x*2].size();//得到左儿子的叶子共有多少个
        if(x*2+1<=n)//如果有右儿子
        {
            dfs(x*2+1);//访问右儿子
            long long ans1=inf,ans2=inf,ansp1=inf,ansp2=inf;
            //分别是 f, t
            for(int i=0;i<dp[x].size();i++)
            {
                if(i<t)//如果这个点是左子树上的点
                {

                    ans1=min(ans1,dp[x*2][i]+1LL*b[x*2]*a[x*2]+(dis[x][i]+b[x*2+1])*a[x*2+1]);
                    ansp1=min(ansp1,dpp[x*2][i]+dis[x][i]*a[x]+1LL*b[x*2+1]*a[x*2+1]);
                }
                else//当这个点是右子树上的点
                {
                    ans2=min(ans2,dp[x*2+1][i-t]+1LL*b[x*2+1]*a[x*2+1]+(dis[x][i]+b[x*2])*a[x*2]);
                    ansp2=min(ansp2,dpp[x*2+1][i-t]+dis[x][i]*a[x]+1LL*b[x*2]*a[x*2]);
                }
            }
            for(int i=0;i<dp[x].size();i++)
            {
                if(i<t)//如果它是左儿子
                {
                    dp[x][i]=ans2+dp[x*2][i];
                    dpp[x][i]=min(dp[x][i],ansp2+dp[x*2][i]);
                }
                else//是右儿子
                {
                    dp[x][i]=ans1+dp[x*2+1][i-t];
                    dpp[x][i]=min(dp[x][i],ansp1+dp[x*2+1][i-t]);
                }
            }
        }
        else//没有右儿子
        {
            for(int i=x;i>=1;i=i/2)
            {
                dp[i].push_back(0);
                dpp[i].push_back(0);
                dis[i].push_back(dep[x]-dep[i]);
            }
            dp[x][0]=1LL*b[x*2]*a[x*2];
            dpp[x][0]=inf;
            dp[x][1]=inf;
            dpp[x][1]=1LL*b[x*2]*a[x];
        }
    }
    else//没有后辈
    {
        for(int i=x;i>=1;i=i/2)
        {
            dp[i].push_back(0);
            dpp[i].push_back(0);
            dis[i].push_back(dep[x]-dep[i]);
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=2;i<=n;i++)
        scanf("%d",&b[i]);
    dfs(1);
    long long ans=inf;
    for(int i=0;i<dp[1].size();i++)
        ans=min(ans,dpp[1][i]);
    printf("%lld\n",ans);
    return 0;
}