The Solution of P2279

· · 题解

本题先前的题解，可以说是没有一篇做到了内容质量与美观程度并存，而这又是一道经典题目，所以打算写一篇完整而又详细美观的题解。

本文含有贪心及 dp 的做法，适合所有语言人群阅读。

0x01 解法

解法 A. 贪心

A-1 贪心思路

我们贪心地先选择深度大的节点，由于一个消防站能够覆盖五层的节点，我们找出当前选择节点 u 的父亲 v 与爷爷 w。

开三个 bool 数组 \text{diz, dio, dit} 分别记录以下信息：

每次遍历时只要寻找一下 u,v,w 对应的 bool 值是否为 \textbf{false} 即可。

以下是不在 w 点染色的情况。

（上述情况的证明非常容易，留作习题。）

这里再记 fa(x) 表示节点 x 的父亲。

若不满足上面提及的情况，我们就可以对 w 进行染色，并将 \text{diz}_w,\text{dio}_{fa(w)},\text{dit}_{fa(fa(w))} 标记为 \textbf{true}。

不管 u,v 的原因是以后都用不上它们了。

还不明白？那就看看下面的图理解。

A-2 贪心实例

考虑如下的一棵树。

其中 \text{dep}_i 表示节点 i 的深度，箭头从每个 x 指向 fa(x)。

我们先按 \text{dep} 从大到小进行排序，先扫描到点 7。

经过对爷爷 4 和父亲 6 的查询，我们发现点 4 可染色，于是便标记 1,3,4，\text{dit}_1 = \textbf{true}。

接下来依次扫描点 5,6,4，发现都不符合要求，不进行染色操作。

当扫描到点 2 时，我们发现它的父亲 1 的 \text{dio} 值为 \textbf{false}。（之前标记的是 1 的 \text{dit} 值），且其他对应的 bool 值都符合要求，于是我们对 2 的爷爷（假设有）进行染色。

答案为 2，完美覆盖了整棵树。

A-3 贪心代码

#include <cstdio>
#include <algorithm>

#define N 2021
using namespace std;
bool diz[N], dio[N], dit[N];
int fa[N], de[N], ind[N];
bool cmp(int a, int b){
    return de[a] > de[b];
}
bool check(int u, int op){
    if(op == 0) return (!diz[u]) && (!dio[u]) && (!dit[u]);
    if(op == 1) return (!diz[u]) && (!dio[u]);
    return !diz[u];
}
int n;
int ans = 0;
int main(){
    scanf("%d", &n);
    ind[1] = 1;
    for(int i = 2 ; i <= n ; i++){
        scanf("%d", &fa[i]);
        de[i] = de[fa[i]] + 1;
        ind[i] = i;
    }
    sort(ind + 1, ind + n + 1, cmp);
    for(int i = 1 ; i <= n ; i++){
        int u = ind[i], v = fa[u], w = fa[v], x = fa[w], y = fa[x];
        if(check(u, 0) && check(v, 1) && check(w, 2))
            ans++, diz[w] = 1, dio[x] = 1, dit[y] = 1;
    }
    printf("%d\n", ans);
    return 0;
}

解法 B. dp

B-2 dp 状态设计

令 d=\text{dep}_i，设 dp_{i,j}\ (1\le i\le n,-2\le j\le 2) 表示所有 i 的子孙与祖先 u 中满足 \text{dep}_u\ge d-j 的点都能被覆盖到。

注意到对于 -2\le j\le k\le 2，覆盖 k 层的情况一定包含了覆盖 j 层的情况，故有 dp_{i,j}\le dp_{i,k}，当下列出现至少覆盖 j 层的字眼时，默认选择 dp 值最小的，即选择 dp_{i,j}。

B-2 dp 转移方程

容易发现，若 i 要覆盖到 2 层，则 i 本身必须被染色且 i 的儿子们也必须覆盖到至少 -2 层，即

dp_{i,2}=1+\sum\limits_{u\in son(i)}dp_{u,-2}

求 dp_{i,1}，我们发现有两种情况：

于是就有式子

dp_{i,1}=\min\left\{dp_{i,2},\min\left\{dp_{u,2}+\sum\limits_{v\in son(i)\land v\ne u}dp_{v,-1}\right\}\right\}

求 dp_{i,0}，有以下两种情况：

于是就有式子：

dp_{i,0}=\min\left\{dp_{i,1},dp_{i,2},\min\left\{dp_{u,1}+\sum\limits_{v\in son(i)\land v\ne u}dp_{v,0}\right\}\right\}

于是有式子：

\begin{aligned} dp_{i,-1}&=\min\left\{dp_{i,0\sim2},\sum\limits_{u\in son(i)}dp_{u,0}\right\}\\ dp_{i,-2}&=\min\left\{dp_{i,-1\sim 2},\sum\limits_{u\in son(i)}dp_{u,-1}\right\} \end{aligned}

我们得到了上述 5 个转移方程后，即可开始转移。

最后的答案是覆盖节点 1 的 0 层所需的最小染色点数，即 dp_{1,0}。

为了方便，我们在开数组的时候，将第二维统一加上 2，将 -2\sim2 变为 0\sim4，防止 RE。

B-3 dp 代码

#include <cstdio>
#include <vector>
#include <algorithm>

#define N 2021
#define INF 99999999
using namespace std;
vector <int> t[N];
int dp[N][5];
int n;
void dfs(int u){
    dp[u][4] = 1, dp[u][1] = 0, dp[u][0] = 0;
    int len = t[u].size();
    for(int i = 0 ; i < len ; i++){
        int v = t[u][i];
        dfs(v);
        dp[u][4] += dp[v][0];
        dp[u][1] += dp[v][2];
        dp[u][0] += dp[v][1];
    }
    if(!len) dp[u][2] = dp[u][3] = 1;
    else{
        dp[u][2] = dp[u][3] = INF;
        int cnt1 = 0, cnt2 = 0;
        // %
        for(int i = 0 ; i < len ; i++){
            int v = t[u][i];
            cnt1 += dp[v][1];
            cnt2 += dp[v][2];
        }
        for(int i = 0 ; i < len ; i++){
            int v = t[u][i];
            dp[u][3] = min(cnt1 - dp[v][1] + dp[v][4], dp[u][3]);
            dp[u][2] = min(cnt2 - dp[v][2] + dp[v][3], dp[u][2]);
        }
        // %
    }
    for(int i = 3 ; i >= 0 ; i--)
        dp[u][i] = min(dp[u][i + 1], dp[u][i]);
}
int main(){
    scanf("%d", &n);
    for(int i = 2 ; i <= n ; i++){
        int u;
        scanf("%d", &u);
        t[u].push_back(i);
    }
    dfs(1);
    printf("%d\n", dp[1][2]);
    return 0;
}

这里计算 dp_{i,0},dp_{i,1} 的部分（注释 \tt \% 的部分）运用了一个先计算总和再减去对应部分的 trick，复杂度有所降低。

0x02 后记

比较

实测表明 dp 耗时 33 ms，贪心耗时 30 ms。

其中，dp 码量更大但转移较为显然；贪心码量小但理解需要再花一点功夫。

修改日志