TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5946
  • 题目
  • P5946[Poi2011]Dynamite
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1.5s,256m
    问题描述

    The Byteotian Cave is composed of n chambers and n-1 corridors that connect them. For every pair of chambers there is unique way to move from one of them to another without leaving the cave. Dynamite charges are set up in certain chambers. A fuse is laid along every corridor. In every chamber the fuses from the adjacent corridors meet at one point, and are further connected to the dynamite charge if there is one in the chamber. It takes exactly one unit of time for the fuse between two neighbouring chambers to burn, and the dynamite charge explodes in the instant that fire reaches the chamber it is inside. We would like to light the fuses in some m chambers (at the joints of fuses) in such a way that all the dynamite charges explode in the shortest time possible since the fuses are lit. Write a program that will determine the minimum such time possible.

    Byteotian Cave的结构是一棵N个节点的树,其中某些点上面已经安置了炸 药,现在需要点燃M个点上的引线引爆所有的炸药。

    某个点上的引线被点燃后的1单位时间内,在树上和它相邻的点的引线会被点燃。如果一个有炸 药的点的引信被点燃,那么这个点上的炸 药会爆炸。
    求引爆所有炸 药的最短时间。

    输入格式

    第一行是两个整数N,M。(1<=m<=n<=300000)
    接下来一行有N个整数Di,第I个数为1表示该点有炸药。
    接下来N-1行每行有两个数A,B,表示A和B之间有一条边。

    输出格式

    最短时间。

    样例输入 1

    7 2
    1 0 1 1 0 1 1
    1 3
    2 3
    3 4
    4 5
    5 6
    5 7

    样例输出 1

    1

    样例输入 2

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

    样例输出 2

    2

    提示

    样例解释: 点燃3,5上的引线。


    来源  bzoj 2525