https://loj.ac/problem/10161

题目描述

??有一个\(m\)个节点的树，可以选择一个度大于\(1\)的节点作为根，并将一些点染为白色或黑色，染色方案因保证根到每个叶子节点的路径上都至少有一个有色节点，并且路径上离叶子结点最近的节点颜色为\(c_i\)

思路

??我们考虑选哪个节点为根不影响答案的选择，因为我们只需要维护叶子节点上方最近的有颜色节点，非叶节点是否为根并不影响答案。我们考虑对于节点\(i\)，如果要将\(i\)染成白色，显然它的叶子节点可以继承它的节点。我们记\(f[i][j]\)表示\(i\)染为\(j\)颜色的代价，而这个颜色是可以继承的。所以我们有两种选择，一是继承其父亲的颜色，二是设立一个新的颜色。继承的话这个点就无须设为应该设的颜色，所以转移方程为\(f[i][0]=\sum min\{f[v][0]-1,f[v][1]\}\)(\(v\)是\(i\)的儿子)。黑色也类似，对于叶子节点将不符的颜色直接设为无穷大即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,INF=1e8;

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

int head[N],to[N<<1],nxt[N<<1],tot;
void add_edge(int x,int y)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
int f[N][3],n;
bool c[N];
void dfs(int u,int fa)
{
    if(u<=n)
    {
        f[u][c[u]]=1;
        f[u][(!c[u])]=INF;
        return ;
    }
    f[u][0]=f[u][1]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==fa)continue ;
        dfs(v,u);
        f[u][0]+=min(f[v][0]-1,f[v][1]);
        f[u][1]+=min(f[v][1]-1,f[v][0]);
    }
}

int main()
{
    int m;
    m=read(),n=read();
    for(int i=1;i<=n;i++)
        c[i]=read();
    for(int i=1;i<m;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);add_edge(y,x);
    }   
    dfs(n+1,0);
    write(min(f[n+1][0],f[n+1][1]));
}

叶子的染色

原文：https://www.cnblogs.com/fangbozhen/p/11838765.html