P3523-[POI2011]DYN-Dynamite

题目:

题目描述:

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.

给一棵树,书上有一些关键节点，要求你选m个点，使得关键节点到这些点中距离的最小值的最大值最小，求这个值

输入格式:

The first line of the standard input holds two integers $n$ and $m$($1\le m\le n\le 300\ 000$), 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 $d_1,d_2,\cdots,d_n$ ($d_i\in {0,1}$), separated by single spaces.

If $d_i=1$, then there is dynamite in the $i$-th chamber, and if $d_i=0$, there is none.The following $n-1$ lines specify the corridors of the cave. Each of them holds two integers $a,b$($1\le a<b\le 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\le 10$ , while in tests worth 40% of the points it holds that $n\le 1\ 000$

输出格式:

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.

样例:

样例输入1:

1
2
3
4
5
6
7
8

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

样例输出1:

1

1

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include "ybwhead/ios.h"
int n, m;
const int maxn = 3e5 + 10;
int a[maxn];
struct edge
{
    int v, nxt;
} e[maxn << 1];
int head[maxn], tot;
void __ADD(int u, int v)
{
    e[++tot] = {v, head[u]};
    head[u] = tot;
}
void add(int u, int v)
{
    __ADD(u, v);
    __ADD(v, u);
}
int ans;
long long f[maxn];
long long g[maxn];
void dfs(int u, int fa, int len)
{
    g[u] = INT_MAX;
    f[u] = -g[u];
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        dfs(v, u, len);
        f[u] = max(f[u], f[v] + 1);
        g[u] = min(g[u], g[v] + 1);
    }
    if (f[u] + g[u] <= len)
        f[u] = -INT_MAX;
    if (g[u] > len && a[u] == 1)
        f[u] = max(f[u], 0ll);
    if (f[u] == len)
        ++ans, g[u] = 0, f[u] = -INT_MAX;
}
int check(int x)
{
    ans = 0;
    dfs(1, 0, x);
    if (f[1] >= 0)
        ++ans;
    return ans <= m;
}
int main()
{
    yin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        yin >> a[i];
    }
    for (int i = 1; i < n; i++)
    {
        int a, b;
        yin >> a >> b;
        add(a, b);
    }
    int l = 0, r = n + 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    yout << l << endl;
}