Dotcpp  /  编程题库  /  信息学奥赛一本通T1583-叶子的染色
题目 2488:

信息学奥赛一本通T1583-叶子的染色

 时间限制: 1s 内存限制: 128MB

题目描述

原题来自：CQOI 2009

给一棵有 m 个节点的无根树，你可以选择一个度数大于 1 的节点作为根，然后给一些节点（根、内部节点、叶子均可）着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点，哪怕是叶子本身。

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

输入格式

第一行包括两个数 m,n，依次表示节点总数和叶子个数，节点编号依次为 1 至 m。

接下来 n 行每行一个 0 或 1 的数，其中 0 表示黑色，1 表示白色，依次为 c1,c2,⋯,cn  的值。

接下来 m−1 行每行两个整数 a,b，表示节点 a 与 b 有边相连。

输出格式

输出仅一个数，表示着色节点数的最小值。

样例输入

5 3
0
1
0
1 4
2 5
4 5
3 5

样例输出

2

提示

数据范围与提示:：

信息学奥赛一本通T1583-叶子的染色

标签
  
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
信息学奥赛一本通TT1262-挖地雷
信息学奥赛一本通T1263-友好城市
信息学奥赛一本通T1258- 数字金字塔
信息学奥赛一本通T1309-回文数
信息学奥赛一本通T1173-阶乘和