洛谷P3523 [POI2011] DYN-Dynamite 题解

题目链接：P3523 [POI2011] DYN-Dynamite

题意：

给定一棵 $n$ 个节点的树，树上有若干个关键点。

现在要你选 $m$ 个点，使得所有关键点到这 $m$ 个点距离的最小值的最大值 $K$ 最小。

输入格式：

第一行给出 $n,m$ ，第二行给出每个点是否是关键点。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示 $u,v$ 之间有一条边。

输出格式：

一行，即 $K$ 的最小值。

数据范围：

$1 \le n,m \le 3\times 10^5$ 。

考虑二分 $K$ ，问题转化为能否选 $m$ 个点，使得这 $m$ 个点与关键点的最小距离均不超过 $K$ 。

可以发现放的点越多，这个最小距离越不可能超过 $K$ 。

于是问题就转化为，选 $k$ 个点，使得这 $k$ 个点与关键点的最小距离均不超过 $K$ ，最小化 $k$ 。

不妨称点 $u$ 覆盖了关键点 $v$ ，当且仅当点 $u$ 到关键点 $v$ 的距离不超过 $K$ 。

注意到对于每个关键点，我们会尽可能晚一些用点去覆盖它。

考虑设 $f_u$ 为 $u$ 所在子树中最远的未被覆盖到的关键点，$g_u$ 为 $u$ 到子树中钦定的点的最小距离。

叶节点的初值为 $f_u = -\infty,~g_u=+\infty$ ，其余节点的初值为

$f_u = \max_{v \in \mathrm{son}(u)}\{f_v\}\\ g_u = \min_{v \in \mathrm{son}(u)}\{g_v\}$

接着考虑需要钦定点的情况，以及边界情况：

若 $f_u + g_u \le K$ ，则不需要钦定点，令 $f_u \gets -\infty$ 即可。
若 $f_u = K$ ，则我们必须要钦定 $u$ 来覆盖它，那么 $f_u \gets -\infty,\,g_u \gets 0,\,k\gets k+1$ 。
若 $g_u > K$ 且 $u$ 是关键点，直接令 $f_u \gets \max\{f_u,0\}$ 即可。

这样点 $u$ 的子树被完全覆盖当且仅当 $f_u=-\infty$ ，记得特判根节点的决策。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(3e5 + 15))

bool vip[N]; vector<int> vec[N];
int n, m, cnt, f[N], g[N];
void dfs(int u, int fa, int mid)
{
    f[u] = -INF; g[u] = INF;
    for(int v : vec[u]) if(v != fa)
    {
        dfs(v, u, mid);
        up(f[u], f[v] + 1); down(g[u], g[v] + 1);
    }
    if(f[u] + g[u] <= mid) f[u] = -INF;
    if(g[u] > mid && vip[u]) up(f[u], 0);
    if(f[u] == mid) { f[u] = -INF; g[u] = 0; ++cnt; }
}
bool check(int mid)
{
    cnt = 0; dfs(1, 0, mid);
    if(f[1] >= 0) ++cnt;
    return cnt <= m;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; rep(i, 1, n) cin >> vip[i];
    rep(i, 1, n - 1)
    {
        static int u, v; cin >> u >> v;
        vec[u].pb(v); vec[v].pb(u);
    }
    int l = 0, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid; else l = mid + 1;
    }
    cout << l << '\n';
    return 0;
}