【Luogu】P3155叶子的染色（树形DP）

题目链接

树形DP水题qwq。

设f[i][j]是以i为根的子树，染成j色，且满足内部需求的最少染色节点数。

设to是x的子节点，那么状态转移方程如此设计：

1、f[i][0]

这个状态表示i不染色，那显然很好办，对于每个to从f[to][1],f[to][2]和f[to][0]里选一个最小的即可。

转移方程$f[x][0]=\sum\limits_{to}min(f[to][1],f[to][2],f[to][0])$

2、f[i][1]

此时i染成黑色。那么对于每个to我们发现，既可以让它继续染白，也可以把本来染成黑色的to改为无色，让染成黑色的i来发挥to的作用。

于是$f[x][1]=\sum\limits_{to}min(f[to][1]-1,f[to][2])$

f[i][2]类似，不再赘述。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cctype>
#include<cstring>
#define maxn 50020
using namespace std;

inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

int f[maxn][3];
int q[maxn];

struct Edge{
    int next,to;
}edge[maxn*2];
int head[maxn],num;
inline void add(int from,int to){
    edge[++num]=(Edge){head[from],to};
    head[from]=num;
}

int root;
int m,n;
void dfs(int x,int fa){
    if(x<=n){
        f[x][q[x]+1]=1;
        f[x][(q[x]^1)+1]=f[x][0]=1000000;
        return;
    }
    int whi=0,bla=0;
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        if(to==fa)    continue;
        dfs(to,x);
        f[x][0]+=min(f[to][1],min(f[to][2],f[to][0]));
        whi+=min(f[to][2]-1,f[to][1]);
        bla+=min(f[to][1]-1,f[to][2]);
    }
    f[x][2]=whi+1;
    f[x][1]=bla+1;
    return;
}
        

int main(){
    m=read(),n=read();
    for(int i=1;i<=n;++i)    q[i]=read();
    for(int i=1;i<m;++i){
        int from=read(),to=read();
        add(from,to);
        add(to,from);
    }
    root=n+1;
    dfs(root,root);
    printf("%d",min(f[root][0],min(f[root][1],f[root][2])));
    return 0;
}

/*
10 5
1 0 1 1 0
1 6
6 2
6 3
7 6
7 4
7 10
10 9
9 8
8 5
*/