luogu 3155

 m 个节点的无根树，选一个根，将一些节点 染成黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点，哪怕是叶子本身。

对于每个叶子节点 u，定义 c[u] 为从根节点到 u 的简单路径上最后一个有色节点的颜色。给出每个 c[u]  的值，设计着色方案使得着色节点的个数最少。

#include <bits/stdc++.h>
using namespace std ;
  const int N=1e4+2,M=5*N;
 int n,m,a[N],f[N][2],nxt[M],go[M],all,hd[N];
 void add(int x,int y){
     go[++all]=y; nxt[all]=hd[x],hd[x]=all;
 }
 void dfs(int x,int fa){
     if(x<=m) return ;
     
     int i,y;
     for(i=hd[x];i;i=nxt[i]){
         y=go[i]; if(fa==y) continue;
         dfs(y,x);
         
         f[x][0]+=min(f[y][0]-1,f[y][1]);
         f[x][1]+=min(f[y][1]-1,f[y][0]);
     }
 }
 int main(){
     int i,x,y; 
     memset(f,0x7f7f3f,sizeof(f));
       cin>>n>>m;
    for(i=1;i<=m;i++) cin>>x,f[i][x]=1;
    
    for(i=1;i<n;i++) {
      cin>>x>>y,add(x,y),add(y,x);
      if(i>m) f[i][0]=f[i][1]=1; 
    }
    f[n][0]=f[n][1]=1;
    dfs(n,0);
    cout<<min(f[n][0],f[n][1]);
 }