洛谷3155 [CQOI2009]叶子的染色

access_time    bookmark 题解    comment 0 条评论    提高+/省选-

题意

一棵无根树,要求根节点到每个叶子的路径上都至少有一个有色节点。

给出根节点到每个叶子节点路径上最后一个有色节点的颜色,求有色节点个数最小值。

其中点数 $N\le 1000$ ,叶子节点个数 $M\le 5021$ 。(我按个人习惯反过来了)

题解

树形dp,用 $f[x][0/1]$ 表示以 $x$ 为根的子树,最后一个有色节点颜色为黑/白的最优情况。

考虑状态转移,如果子节点和自己要求一样,则节点个数不变;如果不一样,就意味着子节点染了自己要求的颜色,节点个数 $+1$ 。得到方程:

$$f[x][i] = \Sigma min(f[y][i],f[y][!i]+1)$$

虽然是无根树,但取哪个为根对答案没有影响(我也不知道怎么证明),所以可以将前 $M$ 个节点设为叶子节点,以 $M+1$ 为根搜索。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[20005];
bool s[10005];
int cnt,head[10005],n,m,a,b,f[10005][2];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    if (x<=m)
    {
        f[x][s[x]]=0;
        f[x][s[x]^1]=1e9;
    }
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        dfs(y,x);
        f[x][0]+=min(f[y][1]+1,f[y][0]);
        f[x][1]+=min(f[y][0]+1,f[y][1]);
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++) s[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(m+1,0);
    printf("%d",min(f[m+1][0],f[m+1][1])+1);
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。