洛谷 P3155 [CQOI2009]叶子的染色解题报告

P3155 [CQOI2009]叶子的染色

题目描述

给一棵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 有边相连。

输出格式：

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

显然是树形DP。

(dp[i][j])表示以(i)为子树外面（注意是“外面”，不是这个点）需染(0,1,2)(即不需要)的最小染色点数

转移：
(dp[i][0]=sum min(dp[son][0],dp[son][2]);)
(dp[i][1]=sum min(dp[son][1],dp[son][2]);)
(dp[i][2]=sum dp[son][2];)

当然有更简单的转移方法。

然后开始推换根。

~~成功没推出来~~

事实上这个题都给了提示，“可以选择一个”，根只要不是度为1的节点都是可以的。

证明：两个相邻的点不可能换根后更优，分6种情况讨论即可。

code:

#include <cstdio>
#include <cstring>
int max(int x,int y) {return x>y?x:y;}
int min(int x,int y) {return x<y?x:y;}
const int N=10010;
int m,n;
int dp[N][3];//以i为子树外面需染0,1,2(即不需要)的最小染色点数
struct Edge
{
    int to,next;
}edge[N*2];
int head[N],cnt=0,used[N];
void add(int u,int v)
{
    edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}

void dfs(int now)
{
    used[now]=1;
    int sum0=0,sum1=0,sum2=0;
    for(int i=head[now];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!used[v])
        {
            dfs(v);
            sum0+=min(dp[v][0],dp[v][2]);
            sum1+=min(dp[v][1],dp[v][2]);
            sum2+=dp[v][2];
        }
    }
    if(now>n)
    {
        dp[now][0]=sum0;
        dp[now][1]=sum1;
        dp[now][2]=min(min(sum0,sum1)+1,sum2);
    }
}
int ans=0x3f3f3f3f;
int color[N];
int main()
{
    scanf("%d%d",&m,&n);
    int u,v;
    for(int i=1;i<=n;i++)
        scanf("%d",color+i);
    for(int i=1;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        dp[i][color[i]]=0;
        dp[i][2]=1;
    }
    dfs(n+1);
    printf("%d
",dp[n+1][2]);
    return 0;
}