1 #include2 #include 3 #define N 10009 4 #define inf 100000 5 using namespace std; 6 int b[N],cnt,n,m,c[N],f[N][2],head[N],next[2*N],u[2*N]; 7 void jia(int a1,int a2) 8 { 9 cnt++;10 next[cnt]=head[a1];11 head[a1]=cnt;12 u[cnt]=a2;13 return;14 }15 void dp(int a1)16 {17 b[a1]=1;18 if(a1<=m)19 {20 f[a1][c[a1]]=1;21 f[a1][c[a1]^1]=inf;22 return;23 }24 else25 f[a1][0]=f[a1][1]=1;26 for(int i=head[a1];i;i=next[i])27 if(!b[u[i]])28 {29 dp(u[i]);30 f[a1][0]+=min(f[u[i]][1],f[u[i]][0]-1);31 f[a1][1]+=min(f[u[i]][1]-1,f[u[i]][0]);32 }33 return;34 }35 int main()36 {37 scanf("%d%d",&n,&m);38 for(int i=1;i<=m;i++)39 scanf("%d",&c[i]);40 for(int i=1;i
树形dp 任意可行的节点做根答案都是一样的,f[i][0]表示i节点染白色,1染黑色,所以如果i节点染白色他的子节点中染白色的节点就不用染了。