洛谷 P3155 [CQOI2009]叶子的染色 题解【DP】【树形DP】

点击量：389

目录

题目描述

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

 

输入输出格式

输入格式：

第一行包含两个正整数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 有边相连。

 

输出格式：

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

 

输入输出样例

输入样例#1：

5 3

0

1

0

1 4

2 5

4 5

3 5

输出样例#1：

2

说明

M<=10000

N<=5021

   这个题一开始是用贪心做的，但是贪心需要顾及的细节太多了，一般贪心只能拿30分，然后改成了DP做法。

   我们首先要证明，根节点的选择对结果没有影响。只要度大于1，任何点都可以为根。我们来看一种情况：有3个度大于1的点，以这三个点为根，对答案均没有影响。

   此时1号照看了2，3，4；如果1，2染色相同，那么它们当然可以互换，1本来就照顾了2，3，4的颜色。 如果1，2染色不同，它们依然可以互换。

   令最优解时1为黑色，2为白色。

   当以1号为根时，2，3，4的白色被1照看，而2是黑色，不需要1的照看，那么这时可以想象有一个根节点是1和2共同的父亲，这样一来，无论父亲是什么颜色，一旦1和2不同，结果都是一样的。由此可以类推到多个度大于1的点。

   这样我们就知道，根节点是不用枚举的。

   接下来的过程就要简单一些了，是普通的树形DP。

   在对一个节点操作时，取得是子结点的最优情况，如果该父节点取黑色，那么就用子节点的黑色-1和子节点的白色比较；白色同理。为什么黑色要-1，是因为父亲染了黑色，孩子就不用染了，而在孩子的状态中，自己是染了色的，所以要将重复的因素扣除。

   而在DP即将结束时，如果这个点是叶子节点，直接返回不变，如果不是叶子，那么自己还需要染一种颜色，将f[x][]++。

   需要注意的是，f数组的初始值。因为我们每次DFS结束后需要给自己染色，因此叶子节点选择自己的颜色置0，否则置1。

   这里细节还是很多的，值得深入思考。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
struct node
{
    int n;
    node *nxt;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[10200],*tail[10200];
int f[10200][2];
int n,m;
int c[10200];
bool used[10200];
void dfs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(used[p->n])
            continue;
        used[p->n]=true;
        dfs(p->n);
        used[p->n]=false;
    }
    //开始dp
    p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(used[p->n])
            continue;
        f[x][0]+=min(f[p->n][0]-1,f[p->n][1]);
        f[x][1]+=min(f[p->n][0],f[p->n][1]-1);
    }
    f[x][0]++;//自己还需要染色
    f[x][1]++;
    return;
}
int main()
{
    int u,v;
    memset(f,0,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&c[i]);
        f[i][1-c[i]]=1;//说明选另一个颜色时自己照看自己，染了一个颜色。
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        tail[u]->nxt=new node(v);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u);
        tail[v]=tail[v]->nxt;
    }
    used[m+1]=true;
    dfs(m+1);
    printf("%d\n",min(f[m+1][0],f[m+1][1]));
    return 0;
}

注：在叶子节点，退出dfs(叶子)时，f是++了的。