猫猫和企鹅

形式化题目

给定一棵 $n$ 个节点的无向树，所有边权为 $1$ 。固定节点 $1$ 为起点，统计与节点 $1$ 的距离 $1 \le dist \leqslant d$ 的节点个数。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:27
 * update_at: 2026-08-12 22:27
 */
// brute.cpp：小数据暴力解，让每只企鹅从自己出发 DFS 找 1 号点，数走过的边数。
// 树中两个点之间的路径唯一，所以一次 DFS 找到 1 号点的步数就是真实距离。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, d;
vector<int> g[MAXN]; // g[u] 保存与 u 相邻的所有点（邻接表）
int vis[MAXN];       // vis[u] 表示当前这次 DFS 是否已经访问过 u，防止往回走

// 从 u 出发找 1 号点，返回找到 1 号点经过的最少边数。
int dist_to_root(int u) {
    vis[u] = 1;
    if (u == 1) return 0;

    int best = MAXN; // 很大的数，表示这个方向没找到 1 号点
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (vis[v]) continue;
        int t = dist_to_root(v);
        if (t + 1 < best) best = t + 1;
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int ans = 0;
    // 每只企鹅分别从自己出发找一次 1 号点，O(n) 次 DFS 只适合小数据。
    for (int i = 2; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if (dist_to_root(i) <= d) ans++;
    }
    cout << ans << endl;

    return 0;
}

这个暴力让每只企鹅（节点 $2..n$ ）各自从自己出发 DFS 找 $1$ 号点，数走过的边数作为距离，再与 $d$ 比较。因为树中两点路径唯一，DFS 找到的路径就是最短路，所以它对小数据完全正确；但每只企鹅都重新遍历一遍树，总复杂度 $O(n^2)$ ，过不了 $10^5$ 的数据。

关键观察：所有企鹅到 $1$ 号点的距离信息可以在一次遍历里全部得到——树边权全为 $1$ ，从 $1$ 号点 BFS 时，层数就是到 $1$ 的距离，且每个点只会被访问一次。

于是正式解就是一次限深 BFS：

从 $1$ 号点出发，dist[1] = 0 入队；
弹出点 u，若 dist[u] == d 则不再扩展（再走一步距离就超过 $d$ ）；
否则遍历邻居，未访问的点记为 dist[v] = dist[u] + 1，计数加一并入队。

dist 数组用 -1 兼任“未访问”标记，既防止无向边走回头路，也保证每个点只被计数一次。 $1$ 号点本身被标记访问但不计数，因为只有它没有企鹅。

样例 BFS 过程

这张 ASCII 图展示样例（d = 1）的 BFS 分层情况：

text

1
2
3
4
5        1 ────────────── 层 0（起点，不计入答案）
       / \
      2   3 ──────────── 层 1（访问到，计数 +1 +1）
     /     \
    4       5 ────────── 层 2（距离 > d，不会被访问到）

从图中看，d = 1 时只有第 1 层的节点 2 和 3 满足条件。层 1 的节点出队时距离已经等于 d，不会再扩展，所以层 2 的 4 和 5 永远到不了。BFS 逐层扩展的顺序，正好把“距离不超过 d”翻译成“前 d 层”，这就是答案 2 的来源。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:27
 * update_at: 2026-08-12 22:27
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, d;
vector<int> g[MAXN]; // g[u] 保存与 u 相邻的所有点（邻接表）
int dist[MAXN];      // dist[u] 表示 u 到 1 号点的距离，-1 表示还没访问过
int ans;             // 可以拜访的企鹅数量（不含 1 号点本身）

// 从 1 号点 BFS，边权全为 1，距离恰好为 d 的点不再扩展。
void bfs() {
    queue<int> q;
    memset(dist, -1, sizeof(dist));
    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // 距离已经是 d 的点，再走一步就超过 d，不需要扩展。
        if (dist[u] == d) continue;

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (dist[v] != -1) continue; // v 已经被访问过，跳过

            dist[v] = dist[u] + 1;
            ans++; // 每发现一个新点，就多一只可以拜访的企鹅
            q.push(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bfs();
    cout << ans << endl;

    return 0;
}

DFS 版本

本题也可以手写限深 DFS 完成：用链式前向星存树，从 $1$ 号点深搜，dep > d 时直接返回剪枝，vis 数组防止沿无向边走回头路，访问到的节点逐个计数。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#include <bits/stdc++.h>
using namespace std;

int n,d;
int cnt;
const int maxn = 1e6+5;
const int maxe = 1e6+5;
bool vis[maxn];

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }
    //返回head[u]
    int operator()(int u){ return h[u]; }
} e;

void dfs(int u,int dep) {
  vis[u]= 1;
  if( dep > d) return ;
  cnt++;
  // cout << u << " " << dep <<endl; 
  for(int i = e(u); i !=-1 ; i= e[i].next)
  {
    int v = e[i].v;
    if( vis[v]) continue;
    dfs(v,dep+1);
  }
}

void init(){
  cin >> n >> d;
  for(int i =1;i<n;i++) {
    int u, v;
    cin >> u >> v;
    e.add2(u,v);
  }
}

int main(int argc, char const *argv[])
{
  init();
  dfs(1,0);
  cout << cnt -1 << endl;
  return 0;
}

注意计数时 cnt 包含了 $1$ 号点本身，最后输出 cnt - 1 才是可拜访的企鹅数。DFS 与 BFS 的时间复杂度同为 $O(n)$ ：每个点最多被访问一次，每条边最多被遍历两次。

复杂度

时间：每个点入队、出队各一次，每条无向边被遍历两次， $O(n)$ 。
空间：邻接表、dist 数组、队列各 $O(n)$ 。

总结

单位边权树上的“距起点不超过 $d$ ”就是一次限深 BFS：层数即距离，距离达到 $d$ 的层停止扩展，访问到的非根节点逐个计数。核心是复用“一次遍历得到全部距离”的想法，把每只企鹅独立求距离的 $O(n^2)$ 压到 $O(n)$ ；-1 兼任未访问标记、根节点不计数这两个细节是这类 BFS 计数题最常见的丢分点。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素暴力（brute.cpp）
  每只企鹅 i 各自 DFS 找 1 号点，数走过的边数     O(n) 每只企鹅
        |
        | 瓶颈：n-1 只企鹅各遍历一遍树，O(n^2)
        v
关键观察
  树边权全为 1，BFS 层数 = 到 1 号点的距离
  距离信息一次遍历全部得到，无需每只企鹅单独算
        |
        v
限深 BFS（main.cpp）
  dist[1] = 0 入队，ans = 0
  出队 u：dist[u] == d 不再扩展
  新邻居 v：dist[v] = dist[u]+1，ans++，入队
  1 号点标记访问但不计数（没有企鹅）
        |
        v
复杂度 O(n)，空间 O(n)

图中三条主线对应“暴力慢在哪里”“观察到什么性质”“正式解如何利用这个性质”。BFS 逐层扩展天然按距离分层，所以“距离不超过 d”变成了“只允许进入前 d 层”，每发现一个节点就对应一只可拜访的企鹅。

目录

形式化题目

思路

样例 BFS 过程

代码

DFS 版本

复杂度

总结

图示解析