洛谷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;
}