题解【NOIP2018提高组D2T3 保卫王国】

声明:本文思路参考zhoutb2333大佬的题解

前面的题解思路都挺清晰的,但是对于对细节不是很熟悉的同学理解起来可能比较困难(比如我),于是就有了这篇题解。

ddp虽然好想,但是码量有点大(~~其实是我不会~~),因此本文用倍增优化树形DP来解决本题。

------------
**题意分析**

给一棵树染色,每个节点染色需要一定的花费,要求相邻两个节点至少要有一个被染色色,给出一些限制条件,求满足每个限制条件的最小花费为多少。

**思路分析**

首先判断无解的情况。显然,只有当$a,b$互为父子关系(这里的父子关系指的是严格相邻),且$x,y$都为0时才无解,其它情况都可以通过多染色来解。

很容易想到树形DP,那么具体状态如何设置呢?对于每个限制条件给出的两个点$a,b$,答案可以由四个部分构成:以$a$为根的子树,以$b$为根的子树,以$lca(a,b)$为根的子树减去以$a$为根的子树和以$b$为根的子树,整棵树减去以$lca(a,b)$为根的子树。因为对$a,b$的限制会影响到从$a$到$b$的链上的染色状态,因此拆成这四部分,这四部分互相不影响。

显然,对$a,b$的限制只会影响到以$lca(a,b)$为根的子树减去以$a$为根的子树和以$b$为根的子树的答案,因此,我们可以将其它三个部分的答案预处理出来,然后DP处理剩下的这一部分。

因此状态可以设定为:$f1[i][1/0]$表示以$i$为根的子树当$i$染色/不染色时的最小花费,$f2[i][1/0]$表示整棵树减去以$i$为根的子树当$i$染色/不染色时的最小花费,$dp[i][1/0][1/0]$表示以$lca(a,b)$为根的子树减去以$i$为根的子树当$i$染色/不染色及$i$的父节点染色/不染色(按顺序对应第二维和第三维)时的最小花费。这样,我们就可以从$a,b$一直DP到$lca(a,b)$处计算答案了。特别地,当当前状态无解时,值设定为INF。

但是这样的时间复杂度显然太大。类似这样在树上多次向上的DP,可以想到利用树上倍增进行优化。更改一下$dp$数组的定义,$dp[i][j][0/1][0/1]$表示以$i$的$2^j$辈祖先为根的子树减去以$i$为根的子树当$i$染色/不染色及$i$的$2^j$辈祖先染色/不染色时的最小花费。

接下来的问题就是如何进行DP了。利用上面的三个数组,我们可以倍增地DP到$lca(a,b)$处。首先,我们先将$a,b$中深度较大的一个向上倍增DP,直到$a,b$处于同一深度;此时若$a=b$,说明它们原本具有祖先与后代的关系,直接输出答案;否则就将$a,b$同时向上倍增DP,直到$lca(a,b)$的子节点处,然后进行最后的处理,输出答案。DP的时候,枚举状态转移即可。

整理一下思路:

1. 预处理出$f1,f2,dp$三个数组
1. 将$a,b$中深度较大的一个向上倍增直到$a,b$处于同一深度
1. 判断此时$a,b$是否相等,如果是,直接输出答案;否则继续向上倍增
1. 将$a,b$倍增到$lca(a,b)$的子节点处,进行最后的处理,输出答案

接下来将对具体的实现步骤进行讲解。

**具体实现**

1. 预处理$f1$数组

很基础的一个树形DP,类似于没有上司的舞会,就不再赘述了。同时也处理出深度数组$d$和倍增祖先数组$f$。

void dfs1(int fa,int x)
{
    f[x][0]=fa,d[x]=d[fa]+1,f1[x][1]=p[x];
    for(int i=head[x],y;i;i=Next[i])
        if(fa!=(y=ver[i]))
        {
            dfs1(x,y);
            f1[x][0]+=f1[y][1];
            f1[x][1]+=min(f1[y][0],f1[y][1]);
        }
}

2. 预处理$f2$数组

当$i$不染色时,$i$的父亲节点必须染色,因此答案就是当$i$的父亲染色时,整棵树减去以$i$的父亲为根的子树的答案,加上以$i$的兄弟(即父亲相同的节点)为根的子树为根的答案。回顾递推$f1$数组的过程,以$i$的兄弟为根的子树为根的答案相当于统计时少了$i$的统计,即$f1[fa][1]-min(f1[i][0],f1[i][1])$,其中$fa$表示$i$的父亲。

当$i$染色时,$i$的父亲染不染色都可以,$i$的父亲染色时和$i$不染色时的答案是一样的,不染色时同理统计,相当于统计$f1$时撤销了对$i$的统计。

void dfs2(int x)
{
    for(int i=head[x],y;i;i=Next[i])
        if(f[x][0]!=(y=ver[i]))
        {
            f2[y][0]=f2[x][1]+f1[x][1]-min(f1[y][0],f1[y][1]);
            f2[y][1]=min(f2[y][0],f2[x][0]+f1[x][0]-f1[y][1]);
            dfs2(y);
        }
}

3. 预处理$dp$数组

先将$dp$数组初始化为无限大。首先先处理dp初值,即$j=0$的情况。

显然,当$i$和$i$的父节点都不染色时,是无解的,不动它;当$i$的父亲染色时,$i$染不染色都可以,因此答案和上面$f2[i][0]$的转移类似,只是不用加上剩下的部分;当$i$的父亲不染色时,$i$必须染色,转移类似,就不再赘述了。

然后就是倍增地处理,对于第$2^j$辈祖先,枚举第$2^{j-1}$辈祖先及$i$和第$2^j$辈祖先的状态进行转移。转移思想也基本类似。

void pre()
{
    memset(dp,0x3f3f,sizeof(dp));
    dfs1(0,1),dfs2(1);//先处理f1,f2数组
    for(int i=1;i<=n;i++)
    {
        dp[i][0][0][1]=dp[i][0][1][1]=f1[f[i][0]][1]-min(f1[i][0],f1[i][1]);//父节点染色
        dp[i][0][1][0]=f1[f[i][0]][0]-f1[i][1];//父节点不染色
    }
    for(int j=1;j<=19;j++)
        for(int i=1;i<=n;i++)
        {
            int fa=f[i][j-1];
            f[i][j]=f[fa][j-1];//先计算祖先
            for(int x=0;x<2;x++)//枚举当前点的状态
                for(int y=0;y<2;y++)//枚举第2^j辈祖先的状态
                    for(int z=0;z<2;z++)//枚举第2^(j-1)辈祖先的状态
                        dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j-1][x][z]+dp[fa][j-1][z][y]);
        }
}

接下来对询问的处理进行讲解。

4. 将$a,b$中深度较大的一个上移,直到$a,b$处于同一深度

我们可以先令深度较大的一个为$a$,若不是,则交换。

定义四个数组$ansa[0/1],ansb[0/1],nowa[0/1],nowb[0/1]$,分别代表$a,b$不染色/染色时最终的答案和当前的答案。具体地说,这个答案就是以当前倍增到的这个祖先为根的子树的答案。

处理之前,因为限制条件,将$a,b$点的另一个状态初始化为INF。

转移的时候,一样地,枚举中间点的状态进行转移。每次转移前,将$nowa$数组初始化为INF;每次转移后,将$nowa$数组的值赋给$ansa$数组,然后将$a$上移。

上移之后,若$a=b$,则直接返回答案。因为当前点是$b$,而限制条件对$b$起作用,因此答案就是$ansa[y]+f2[a][y]$,即以$b$为根的子树的答案加上剩下部分的答案。

    if(d[a]<d[b])
        swap(a,b),swap(x,y);//令x为深度较大的点
    ansa[1-x]=ansb[1-y]=INF;
    ansa[x]=f1[a][x],ansb[y]=f1[b][y];//初值
    for(int j=19;j>=0;j--)//倍增
        if(d[f[a][j]]>=d[b])//上移到同一深度
        {
            nowa[0]=nowa[1]=INF;//初始化
            for(int u=0;u<2;u++)//枚举2^j辈祖先的状态
                for(int v=0;v<2;v++)//枚举当前点的状态
                    nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
            ansa[0]=nowa[0],ansa[1]=nowa[1],a=f[a][j];//数组值转移
        }
    if(a==b)
        return ansa[y]+f2[a][y];//相等直接返回

5. 将$a,b$同时上移到$lca(a,b)$的子节点处

与上一步类似,只是同时上移,就不赘述了。

    for(int j=19;j>=0;j--)
        if(f[a][j]!=f[b][j])
        {
            nowa[0]=nowa[1]=nowb[0]=nowb[1]=INF;
            for(int u=0;u<2;u++)
                for(int v=0;v<2;v++)
                {
                    nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
                    nowb[u]=min(nowb[u],ansb[v]+dp[b][j][v][u]);
                }
            ansa[0]=nowa[0],ansa[1]=nowa[1],ansb[0]=nowb[0],ansb[1]=nowb[1],a=f[a][j],b=f[b][j];
        }

6. 对$a,b,lca(a,b)$的状态进行枚举,进行最后的处理

还是一样的思想,若$lca(a,b)$染色,则$a,b$染不染色都行;否则$a,b$必须染色。式子看起来很长,实际上只是之前的式子多了一个节点罢了。

int fa=f[a][0];
    ans0=f1[fa][0]-f1[a][1]-f1[b][1]+f2[fa][0]+ansa[1]+ansb[1];//lca(a,b)不染色
    ans1=f1[fa][1]-min(f1[a][0],f1[a][1])-min(f1[b][0],f1[b][1])+f2[fa][1]+min(ansa[0],ansa[1])+min(ansb[0],ansb[1]);//lca(a,b)染色
    return min(ans0,ans1);

完结撒花~

(所以对于正解来说type并没有什么用,不过在考场上打不出正解的时候确实是拿部分分的一个好助手)

------------
最后奉上完整代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e5,M=3e5,L=20;
const ll INF=1e17;
int n,m,tot;
int p[N],d[N],f[N][L];
int head[N],ver[2*M],Next[2*M];
ll ans0,ans1;
ll nowa[2],nowb[2],ansa[2],ansb[2],f1[N][2],f2[N][2],dp[N][L][2][2];
string tp;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
    ver[++tot]=x,Next[tot]=head[y],head[y]=tot;
}
void dfs1(int fa,int x)
{
    f[x][0]=fa,d[x]=d[fa]+1,f1[x][1]=p[x];
    for(int i=head[x],y;i;i=Next[i])
        if(fa!=(y=ver[i]))
        {
            dfs1(x,y);
            f1[x][0]+=f1[y][1];
            f1[x][1]+=min(f1[y][0],f1[y][1]);
        }
}//1. 预处理 $f1$ 数组
void dfs2(int x)
{
    for(int i=head[x],y;i;i=Next[i])
        if(f[x][0]!=(y=ver[i]))
        {
            f2[y][0]=f2[x][1]+f1[x][1]-min(f1[y][0],f1[y][1]);
            f2[y][1]=min(f2[y][0],f2[x][0]+f1[x][0]-f1[y][1]);
            dfs2(y);
        }
}//2. 预处理 $f2$ 数组
void pre()
{
    memset(dp,0x3f3f,sizeof(dp));
    dfs1(0,1),dfs2(1);
    for(int i=1;i<=n;i++)
    {
        dp[i][0][0][1]=dp[i][0][1][1]=f1[f[i][0]][1]-min(f1[i][0],f1[i][1]);
        dp[i][0][1][0]=f1[f[i][0]][0]-f1[i][1];
    }
    for(int j=1;j<=19;j++)
        for(int i=1;i<=n;i++)
        {
            int fa=f[i][j-1];
            f[i][j]=f[fa][j-1];
            for(int x=0;x<2;x++)
                for(int y=0;y<2;y++)
                    for(int z=0;z<2;z++)
                        dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j-1][x][z]+dp[fa][j-1][z][y]);
        }
}//3. 预处理 $dp$ 数组
bool check(int a,int x,int b,int y)
{
    return !x && !y &&(f[a][0]==b || f[b][0]==a);
}
ll ask(int a,int x,int b,int y)
{
    if(d[a]<d[b])
        swap(a,b),swap(x,y);
    ansa[1-x]=ansb[1-y]=INF;
    ansa[x]=f1[a][x],ansb[y]=f1[b][y];
    for(int j=19;j>=0;j--)
        if(d[f[a][j]]>=d[b])
        {
            nowa[0]=nowa[1]=INF;
            for(int u=0;u<2;u++)
                for(int v=0;v<2;v++)
                    nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
            ansa[0]=nowa[0],ansa[1]=nowa[1],a=f[a][j];
        }
    if(a==b)
        return ansa[y]+f2[a][y];//4. 将 $a,b$ 中深度较大的一个上移,直到 $a,b$ 处于同一深度
    for(int j=19;j>=0;j--)
        if(f[a][j]!=f[b][j])
        {
            nowa[0]=nowa[1]=nowb[0]=nowb[1]=INF;
            for(int u=0;u<2;u++)
                for(int v=0;v<2;v++)
                {
                    nowa[u]=min(nowa[u],ansa[v]+dp[a][j][v][u]);
                    nowb[u]=min(nowb[u],ansb[v]+dp[b][j][v][u]);
                }
            ansa[0]=nowa[0],ansa[1]=nowa[1],ansb[0]=nowb[0],ansb[1]=nowb[1],a=f[a][j],b=f[b][j];
        }//5. 将 $a,b$ 同时上移到 $lca(a,b)$ 的子节点处
    int fa=f[a][0];
    ans0=f1[fa][0]-f1[a][1]-f1[b][1]+f2[fa][0]+ansa[1]+ansb[1];
    ans1=f1[fa][1]-min(f1[a][0],f1[a][1])-min(f1[b][0],f1[b][1])+f2[fa][1]+min(ansa[0],ansa[1])+min(ansb[0],ansb[1]);
    return min(ans0,ans1);//6. 对 $a,b,lca(a,b)$ 的状态进行枚举,进行最后的处理
}
int main()
{
    scanf("%d%d",&n,&m);cin>>tp;
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    pre();
    for(int i=1,a,x,b,y;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&x,&b,&y);
        if(check(a,x,b,y))
        {
            puts("-1");
            continue;
        }
        printf("%lld\n",ask(a,x,b,y));
    }
    return 0;
}
上一篇:slide效果


下一篇:Noip2018 填数游戏