[bzoj 2525][Poi2011] Dynamite

Description

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.

Input

The first line of the standard input holds two integers n and m (1<=M<=N<=300000)
, separated by a single space, that denote, respectively, the number of chambers in the cave and the number of chambers in which fire can be set to the fuses. The chambers are numbered from 1 to n . The next line contains  n integers d1,d2…dn (Di\in{0,1}, separated by single spaces. If Di=1 , then there is dynamite in the -th chamber, and if di=0 , there is none. The following n -1 lines specify the corridors of the cave. Each of them holds two integers a,b (a<=a<b<=n), separated by a single space, denoting that there is a corridor connecting the chambers a and b . Every corridor appears exactly once in the description.
You may assume that in tests worth 10% of the points it holds additionally that n<= 10, while in tests worth 40% of the points it holds that N<=1000.

Output

The first and only line of the standard output should hold a single integer, equal to the minimum time it takes from lighting the fuses to the explosion of all the charges.

Sample Input

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

Sample Output

1

Solution

题目大意:给一棵树,树上有一些关键点,现在选择至多M个点点燃,每秒向连接的点扩展,最小化每个选择的点到关键点的最小值的值中的最大值。

首选最大值最小,容易想到二分答案

那么问题转化为验证是否能选M个点使得所有选择点到每个关键点的距离中的最小值均不超过x

考虑树形贪心,我们从叶子节点向上扫,对于每一个子树,出于贪心的思路,我们关心的只是没有被点燃的但需要点燃的点到这棵子树的根的最大距离F[x],以及被点燃的点到这棵子树的根的最近距离G[x]

我们有五种情况:

  1. 根节点需要点燃,子树内被点燃的点到这棵子树的根的最近距离>x
  2. 根节点需要点燃,子树内被点燃的点到这棵子树的根的最近距离\leq x
  3. 根节点不需要点燃,子树内不存在需要点燃的点
  4. 根节点不需要点燃,子树内存在需要点燃的点,且该点到根的距离加上子树内被点燃的点到根的最近距离\leq x
  5. 根节点不需要点燃,子树内存在需要点燃的点,且该点到根的距离加上子树内被点燃的点到根的最近距离>x

对于情况1,2,可以合并起来,因为与其经过根节点,不如不经过

所以对于这种情况的处理方式是,更新F[x]=max(0,F[x])

对于情况3,直接记F[x]=-\infty

对于情况4,意味着这棵子树内没有被点燃的点可以由已经被点燃的点在时限内点燃,故删掉这棵子树,即F[x]=-\infty

对于情况5,意味着这棵子树的根必须要点燃,Cur++,然后删掉这棵子树F[x]=-\infty,以及更新最近的点燃点G[x]=0

此外,注意特判根的情况

时间复杂度O(n)

 

发表评论