[luogu3155 CQOI2009] 叶子的染色（树形dp）-白红宇

[luogu3155 CQOI2009] 叶子的染色（树形dp）

阅读量：5052 次

发布时间：2019-06-12

本文共 1120 字，大约阅读时间需要 3 分钟。

Solution

十分简单的树形dpQwQ，转移关系：父亲染了儿子不用染

只需要确定根就是简单树形dp，而其实根可以随便取一个非叶子节点

可以分情况讨论发现答案并不会改变

Code

//By Menteur_Hxy#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define Re register#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)using namespace std;inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x*f;}const int N=1e4+10,INF=0x3f3f3f3f;int n,m;int f[N][2],col[N];vector 
           
             V[N];void dfs(int u,int pre) { f[u][0]=f[u][1]=1; if(u<=m) f[u][!col[u]]=INF; int siz=V[u].size(),v; Fo(i,0,siz-1) if((v=V[u][i])!=pre) { dfs(v,u); f[u][1]+=min(f[v][1]-1,f[v][0]); f[u][0]+=min(f[v][0]-1,f[v][1]); }}int main() { n=read(),m=read();//因习惯n,m互换 Fo(i,1,m) col[i]=read(); Fo(i,1,n-1) { int a=read(),b=read(); V[a].push_back(b); V[b].push_back(a); } dfs(m+1,0); printf("%d",min(f[m+1][0],f[m+1][1])); return 0;}