题意

给定一棵树,一个选定的点可以覆盖距离小于等于二的点,求最少选点个数使整棵树被覆盖

思路

定义状态 f_{u,s}s\in\lbrace0,1,2,3,4\rbrace)分别表示当前子树根为 u,满足状态 s 的最小消防局个数:

  • $s=0$,表示当前子树全被覆盖,子树的父亲及二级祖先也被覆盖的情况
  • $s=1$,表示当前子树全被覆盖,子树的父亲也被覆盖的情况
  • $s=2$,表示当前子树全被覆盖的情况
  • $s=3$,表示当前子树的所有孩子及孩子们的子树全部被覆盖的情况($u$ 不一定被覆盖)
  • $s=4$,表示当前子树的所有孙子及孙子们的子树全部被覆盖的情况($u$ 及 $u$ 的孩子们不一定被覆盖)

易知 f_{u,0}\ge f_{u,1}\ge f_{u,2} \ge f_{u,3}\ge f_{u,4}(显然)
考虑转移,下面方程中令 vv’u 的孩子

f_{u,0}=\sum f_{v,4}

这是一个比较显然的贪心,因为二级祖先被覆盖说明必有一个消防局设立在 u 上,所以易知 u 的孙子们肯定被覆盖了,所以选择 f_{v,4} 来覆盖他儿子的孙子;

f_{u,1}=\min\lbrace f_{v’,0}+\sum_{v\not=v’}f_{v,3}\rbrace

此时 u 的父亲要被覆盖,说明 u 的儿子至少要选一个,即 f_{v’,0}。选了的那个儿子同时又可以覆盖其他儿子,所以是 f_{v,3}

f_{u,2}=\min\lbrace f_{v’,1}+\sum_{v\not=v’}f_{v,2}\rbrace

此时 u 及其子树要被覆盖,所以必须选一个 f_{v’,1} 使 u 本身被覆盖,然后其他儿子自身也要被覆盖,所以其他的要选 f_{v,2}

f_{u,3}=\sum f_{v,2}

f_{u,4}=\sum f_{v,3}

这两个方程比较显然

实现

#include <cstdio>
#include <cctype>
#include <cstring>

const int maxn=1005;
int head[maxn],to[maxn<<1],nxt[maxn<<1],cnt;
int n;

inline void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    return;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int f[maxn][5];

void dfs(int u,int fa)
{
    f[u][0]=1;
    f[u][3]=f[u][4]=0;
    int sum2=0,sum3=0;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)
            continue;
        dfs(v,u);
        f[u][0]+=f[v][4];
        f[u][3]+=f[v][2];
        f[u][4]+=f[v][3];
        sum2+=f[v][2];
        sum3+=f[v][3];
    }
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)
            continue;
        f[u][2]=min(f[u][2],sum2-f[v][2]+f[v][1]);
        f[u][1]=min(f[u][1],sum3-f[v][3]+f[v][0]);
    }
    f[u][1]=min(f[u][1],f[u][0]);
    f[u][2]=min(f[u][2],f[u][1]);
    f[u][3]=min(f[u][3],f[u][2]);
    f[u][4]=min(f[u][4],f[u][3]);
    return;
}

int main()
{
    n=read();
    for(int i=2;i<=n;i++)
    {
        int j=read();
        add(i,j);
        add(j,i);
    }
    memset(f,0x3f,sizeof f);
    dfs(1,0);
    printf("%d\n",f[1][2]);
    return 0;
}
最后修改日期:2020年11月17日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。