洛谷 P2279 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-23 19:51:58

发布于：北京

7阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个基地和连接他们的 $n-1$ 条边
允许：
要求安装最少的消防站点使得所有基地都可以被覆盖
当节点 $i$ 被安装消防站点时，所有与 $i$ 相隔 $\le2$ 条边的都可以被覆盖
限制：
基地形成树形结构

1.3 题目数据范围与猜测

$1 \le n \le 1000$

1.4 一句话概括题意

有 $n$ 个节点， $n-1$ 条边，形成树形结构。求覆盖所有节点的最小节点数量

2 题目破题推导

2.1 从树形结构入手

因为“距离为 $2$ ”，因此对于每个节点，有如下可能性：

提前约定好，把当前节点称作点u，当前节点的孩子称作v，当前节点的孙子称作w，当前节点的父亲称作f，当前节点的祖父称作g

u放消防站点，这样可以覆盖到uvwfg
花费为：1+所有v覆盖他们的w所需最小值
1代表u放站点，因为只有这样才能覆盖到g
这里求所有v覆盖他们的w所需最小值的原因是u放站点覆盖不到曾孙子，所以需要v的w他们单独覆盖
覆盖到uf
u 不放站，枚举选出一个儿子 v 建造消防站；
v 建站可以护住 u，整套方案向上能够覆盖 u 的父亲 f。
其余兄弟 v' 只能被 v 的消防站刚好护住自身，护不住 v' 的孩子。
花费 = min (dp [v][0] + 所有其他 v'「覆盖到 v' 自身层级」的代价)
覆盖到u
u 不放站，依靠孙子身上的消防站保护 u；
枚举选出儿子 v，v 内部的方案可以向上保护 v（dp [v][1]），这条分支的孙子消防站距离 u 刚好为 2，护住 u。
其余兄弟 v' 无法得到任何跨分支支援，整棵子树全部自给自足。
花费 = min ( v能覆盖到u + 所有其他 v'「自给自足覆盖全部子树 )
第四种
u 不放站，但 u 的父亲 f 建有消防站。
此时 u 可以被父亲 f 覆盖，因为父亲到 u 的距离为 1。
但是父亲 f 的消防站距离 u 的孙子 w 为 3，无法覆盖到孙子层。
因此，u 的每个儿子 v 都需要保证自身及其子树被完整覆盖。
也就是说，u 的所有儿子 v 都需要进入 “v 子树自行全覆盖” 的状态。
第五种
u 不放站，但 u 的祖父 g 建有消防站。
此时祖父 g 到 u 的距离为 2，因此 u 可以被祖父覆盖。
但是，祖父 g 到 u 的儿子 v 的距离为 3，无法覆盖 u 的儿子层。
因此，u 的每个儿子 v 都不能依赖祖父 g 的消防站，而需要自己处理 v 及其子树。
又因为 u 本身没有建站，所以对于 v 来说，它并没有被 u 覆盖。
因此，每个儿子 v 需要进入 “v 子树自行全覆盖” 的状态。

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：树形结构，动态求取最大值 $\longrightarrow$ $\huge{树形dp}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1111;
vector<int> g[N];
int dp[N][5];
void dfs(int u, int fa){
    bool leaf = true;
    for (int v : g[u]){
        if (v == fa) continue;
        leaf = false;
        dfs(v, u);
    }
    if (leaf){
        dp[u][2] = dp[u][1] = dp[u][0] = 1;
        dp[u][3] = dp[u][4] = 0;
        return ;
    }
    //
    int sum = 0;
    for (int v : g[u]){
        if (v == fa) continue;
        sum += dp[v][4];
    }
    dp[u][0] = 1 + sum;
    //
    for (int v : g[u]){
        if (v == fa) continue;
        sum = 0;
        for (int vv : g[u]){
            if (vv == fa || vv == v) continue;
            sum += dp[vv][3];
        }
        dp[u][1] = min(dp[u][1], dp[v][0] + sum);
    }
    //
    for (int v : g[u]){
        if (v == fa) continue;
        sum = 0;
        for (int vv : g[u]){
            if (vv == fa || vv == v) continue;
            sum += dp[vv][2];
        }
        dp[u][2] = min(dp[u][2], dp[v][1] + sum);
    }
    //
    sum = 0;
    for (int v : g[u]){
        if (v == fa) continue;
        sum += dp[v][2];
    }
    dp[u][3] = sum;
    //
    sum = 0;
    for (int v : g[u]){
        if (v == fa) continue;
        sum += dp[v][3];
    }
    dp[u][4] = sum;
    //
    for (int i = 1;i <= 4;i++){
        dp[u][i] = min(dp[u][i], dp[u][i - 1]);
    }
}

int main(){

    cin >> n;
    if (n == 1){
        cout << 1;
        return 0;
    }
    for (int i = 2;i <= n;i++){
        int a;
        cin >> a;
        g[i].push_back(a);
        g[a].push_back(i);
    }
    memset(dp, 0x3f, sizeof(dp));
    dfs(1, -1);
    cout << dp[1][2];
    
    return 0;
}