[CQOI2009] 叶子的颜色解题报告(树形DP)

2022-08-13 21:02:56

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1304

Description

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

Input

第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。

Output

仅一个数，即着色结点数的最小值。

Sample Input

5 3
0
1
0
1 4
2 5
4 5
3 5

Simple Output

HINT

M<=10000

N<=5021

这是一道树形DP

首先我们明确，对于任意一个最优方案，我们都可以把它改变成根节点是染色的情况。什么意思呢？就是我可以把其中某个染色的点改成透明的，然后根节点染色，产生一样的效果。请读者自行画几张图，大概就会明白。

于是我们就得出选任何一个非叶子结点做根其实都是一样的

并且我们设计的DP只需要两个状态就可以了，dp[x][0/1]代表以x为根节点的子树染成0/1的最少染色节点数，状态转移方程如下：

dp[x][1]+=min(dp[e[i].to][1]-1,dp[e[i].to][0])
dp[x][0]+=min(dp[e[i].to][1],dp[e[i].to][0]-1)

若是当前点x染成黑色，那么他的儿子中黑色的点就可以变成透明的，对结果没有影响。白色同理。

如果x是叶子结点，若它的c值代表黑色，则dp[x][1]的最小染色数我们设为inf，这是为了排除这个决策

下面附上代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

const int inf=1e9+;

int m,n,k=;

int head[maxn],c[maxn],dp[maxn][];

struct EDGE

{

    int to,next;

}e[maxn];

void add(int u,int v)

{

    e[++k].next=head[u];e[k].to=v;head[u]=k;

}

void dfs(int x,int fa)

{

    if(x<=n)

    {

        dp[x][c[x]]=;

        dp[x][c[x]^]=inf;

        return;

    }

    dp[x][]=dp[x][]=;

    for(int i=head[x];i;i=e[i].next)

    {

        if(e[i].to==fa) continue;

        dfs(e[i].to,x);

        dp[x][]+=min(dp[e[i].to][]-,dp[e[i].to][]);

        dp[x][]+=min(dp[e[i].to][],dp[e[i].to][]-);

    }

}

int main()

{

    int ans;

    scanf("%d%d",&m,&n);

    for(int i=;i<=n;i++)

    scanf("%d",&c[i]);

    for(int i=;i<m;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v);add(v,u);

    }

    dfs(n+,);

    ans=min(dp[n+][],dp[n+][]);

    printf("%d\n",ans);

}

码农公寓