猫猫和企鹅

GitHub跳转原题关系图返回列表

从 1 号点 BFS，统计距离不超过 d 的非根节点。

OJ: luogu

题目 ID: P5908

难度:普及

标签:树BFS队列python

日期: 2026-07-17 02:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

树根为 1，统计距离根不超过 d 的企鹅数量，根节点本身没有企鹅。

思路

树边权全为 1，所以从 1 做 BFS 即可得到最短距离。弹出距离为 d 的节点后不再扩展，访问到的新节点就是一只可拜访的企鹅。

Python 知识

  • collections.deque 的 popleft 是真正的 O(1) 队列操作。
  • 邻接表用列表的列表表达无向树，遍历代码直观。
  • 距离数组用 -1 同时表示“未访问”。

代码

python
import sys
from collections import deque


input = sys.stdin.buffer.readline
n, limit = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

distance = [-1] * (n + 1)
distance[1] = 0
queue = deque([1])
answer = 0
while queue:
    node = queue.popleft()
    if distance[node] == limit:
        continue
    for neighbor in graph[node]:
        if distance[neighbor] == -1:
            distance[neighbor] = distance[node] + 1
            answer += 1
            queue.append(neighbor)
print(answer)

原有 C++ 版本仍保留：

cpp
/**
 * 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-07-17 01:04
 * update_at: 2026-07-17 01:04
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

时间 O(n)，空间 O(n)。

总结

单位边树上的“距离不超过阈值”就是一次限深 BFS。