P3942 将军令

· · 题解

P3942 将军令

若一个点被选择，则它能覆盖到与其距离小于等于 K 的点，求最少选择多少个点使得整棵树被覆盖。

注意到 K 很小，考虑dp。

设 \ f_{u,j} \ 为 \ \left\{ \begin{aligned} &点 \ u \ 被自己控制时的最小花费& j=0& \\ &点 \ u \ 被子树内距离为 \ j \ 的点控制时的最小花费& 0\lt j\le K& \\ &点 \ u \ 被\textcolor{red}{子树外}距离为 \ j-K \ 的点控制时的最小花费& K\lt j\le 2K& \\ \end{aligned} \right.

考虑初始化，显然有

f_{u,j} = \left\{ \begin{aligned} &1& j=0& \\ &INF& 0\lt j\le K& \\ &0& K\lt j\le 2K& \\ \end{aligned} \right.

考虑转移，设 son_u 为点 u 的儿子集合，dis_{u,v} 为 u,v 两点的距离。

当 j=0 时，点 u 被自己控制，显然所有 v\in son_u 可以随便，于是有

f_{u,j}=\sum_{v\in son_u} \min_{k=0}^{2K} \{f_{v,k}\}

当 0\lt j\le K 时，点 u 被子树内一个使得 dis_{u,t}=j 的点 t 控制。

先考虑包含点 t 的点 s\in son_u，显然有 dis_{s,t}=dis_{u,t}-1，故 f_{u,j} 要加上 f_{s,j-1}。

我们设 mn_v 为点 v\in son_u 对 f_{u,j} 的贡献，接下来考虑点 v\in son_u \land v\ne s，有两种情况：

  1. 若点 v 只能被其子树内的点控制，则可以随便选，即 mn_v=\min\limits_{k=0}^{K} \{f_{v,k}\}。
  2. 当且仅当 dis_{v,t}=dis_{u,t}+1\le K，点 v 还能被刚才我们选出的点 t 控制，于是有 mn_v=\min\{\min\limits_{k=0}^{K} \{f_{v,k}\},f_{v,K+j+1}\}。

于是我们得到

f_{u,j}=\min_{s\in son_u} \{f_{s,j-1}+\sum_{v\in son_u \land v \ne s} mn_v\}

为了方便取到最优的点 s 来转移，我们令 sum=\sum\limits_{v\in son_u} mn_v，将方程变化一下，有

f_{u,j}=\min_{s\in son_u} \{f_{s,j-1}+sum-mn_s\}

当 K\lt j\le 2K 时，点 u 被子树外一个使得 dis_{u,t}=j-K 的点 t 控制。

类似地，我们设 mn_v 为点 v\in son_u 对 f_{u,j} 的贡献，同样有两种情况：

  1. 若点 v 只能被其子树内的点控制，则可以随便选，即 mn_v=\min\limits_{k=0}^{K} \{f_{v,k}\}。
  2. 当且仅当 dis_{v,t}=dis_{u,t}+1\le K，点 v 还能被点 t 控制，于是有 mn_v=\min\{\min\limits_{k=0}^{K} \{f_{v,k}\},f_{v,j+1}\}。

于是有

f_{u,j}=\sum_{v\in son_u} mn_v

至此我们得到了全部的转移。

最后考虑统计答案，我们令 1 为根，由于 1 不存在子树外的情况，故有

ans=\min_{j=0}^{K} \{f_{1,j}\}

复杂度 O(NK)，常数还行。

int f[Maxn][Maxk * 2];
void dfs(int u, int lst) {
    f[u][0] = 1;
    for (int j = 1; j <= K; ++j) f[u][j] = INF;
    for (int j = K + 1; j <= 2 * K; ++j) f[u][j] = 0;
    for (int i = head[u]; i; i = eg[i].pre) {
        int v = eg[i].to;
        if (v == lst) continue;
        dfs(v, u);
        int mn = INF;
        for (int k = 0; k <= 2 * K; ++k) mn = min(mn, f[v][k]);
        f[u][0] += mn;
    }
    for (int j = 1; j <= K; ++j) {
        static int mn[Maxn];
        int sum = 0;
        for (int i = head[u]; i; i = eg[i].pre) {
            int v = eg[i].to;
            if (v == lst) continue;
            mn[v] = INF;
            for (int k = 0; k <= K; ++k) mn[v] = min(mn[v], f[v][k]);
            if (K + j + 1 <= 2 * K) mn[v] = min(mn[v], f[v][K + j + 1]);
            sum += mn[v];
        }
        for (int i = head[u]; i; i = eg[i].pre) {
            int v = eg[i].to;
            if (v == lst) continue;
            f[u][j] = min(f[u][j], sum - mn[v] + f[v][j - 1]);
        }
    }
    for (int j = K + 1; j <= 2 * K; ++j) {
        for (int i = head[u]; i; i = eg[i].pre) {
            int v = eg[i].to;
            if (v == lst) continue;
            int mn = INF;
            for (int k = 0; k <= K; ++k) mn = min(mn, f[v][k]);
            if (j + 1 <= 2 * K) mn = min(mn, f[v][j + 1]);
            f[u][j] += mn;
        }
    }
}
// for (int j = 0; j <= K; ++j) ans = min(ans, f[1][j]);