网络延时

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

将交换机和电脑建成一棵树，通过两次 BFS 求树的直径。

OJ: shumeng

题目 ID: CSP201503D

难度:普及-

标签:树BFS树的直径

日期: 2026-07-31 16:21

形式化题目

有 $n$ 台交换机与 $m$ 台电脑，交换机按层级组成一棵以 $1$ 号交换机为根的树，每台电脑直接连到某一台交换机上。消息每经过一条连接算一步，问任意两台设备（电脑或交换机）之间传递消息最多需要多少步，即树上所有点对的最大距离（树的直径）。

思路

先看一个小数据基准：从每个节点出发做一次 BFS，统计所有可达距离的最大值。

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-07-31 16:21
 * update_at: 2026-08-17 22:52
 */
// brute.cpp：小数据基准，从每个节点做一次 BFS 求最远距离。
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;
    int total_nodes = n + m;
    vector<vector<int> > graph(total_nodes + 1);
    for (int child = 2; child <= n; child++) {
        int parent;
        cin >> parent;
        graph[parent].push_back(child);
        graph[child].push_back(parent);
    }
    for (int computer = 1; computer <= m; computer++) {
        int parent;
        cin >> parent;
        int node = n + computer;
        graph[parent].push_back(node);
        graph[node].push_back(parent);
    }

    int answer = 0;
    for (int start = 1; start <= total_nodes; start++) {
        vector<int> distance(total_nodes + 1, -1);
        queue<int> q;
        q.push(start);
        distance[start] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            answer = max(answer, distance[u]);
            for (int i = 0; i < (int)graph[u].size(); i++) {
                int v = graph[u][i];
                if (distance[v] != -1) continue;
                distance[v] = distance[u] + 1;
                q.push(v);
            }
        }
    }
    cout << answer << '\n';

    return 0;
}

brute.cpp 对每个起点都跑一遍 BFS，时间复杂度为 $O(N^2)$ ，只适合小数据，但逻辑最直接，适合对拍。

关键观察

把每台电脑也当作一个节点挂到它连接的交换机上，整个网络仍然是一棵树。题目要求的最大步数就是这棵树的直径。

两次 BFS

无权树求直径的经典做法：

从任意节点（例如 $1$ ）BFS，找到离它最远的节点 $u$ ；
再从 $u$ 出发 BFS，最远距离就是树的直径。

两步各做一次 BFS，总复杂度为 $O(N)$ 。

代码

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:52
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;
vector<int> graph[MAXN]; // 邻接表存树：交换机 1..n，电脑编号为 n+1..n+m

// 从 start 出发 BFS，返回 {最远节点, 到该节点的距离}。
pair<int, int> bfs(int start, int total_nodes) {
    vector<int> distance(total_nodes + 1, -1);
    queue<int> q;
    q.push(start);
    distance[start] = 0;
    int farthest = start;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (distance[u] > distance[farthest]) farthest = u;
        for (int i = 0; i < (int)graph[u].size(); i++) {
            int v = graph[u][i];
            if (distance[v] != -1) continue;
            distance[v] = distance[u] + 1;
            q.push(v);
        }
    }
    return make_pair(farthest, distance[farthest]);
}

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

    int n, m;
    cin >> n >> m;
    // 交换机按树状结构连接，第 i 台交换机连到上一层的交换机。
    for (int child = 2; child <= n; child++) {
        int parent;
        cin >> parent;
        graph[parent].push_back(child);
        graph[child].push_back(parent);
    }
    // 每台电脑作为新的叶子节点挂在对应的交换机上。
    for (int computer = 1; computer <= m; computer++) {
        int parent;
        cin >> parent;
        int node = n + computer;
        graph[parent].push_back(node);
        graph[node].push_back(parent);
    }

    // 整张网络是一棵树，树的直径 = 两次 BFS：任取一点找最远点，再从该点找最远距离。
    int total_nodes = n + m;
    int endpoint = bfs(1, total_nodes).first;
    cout << bfs(endpoint, total_nodes).second << '\n';

    return 0;
}

复杂度

时间：两次 BFS 各遍历一遍所有节点， $O(N)$ ，其中 $N = n + m$ 。
空间：邻接表存储整棵树， $O(N)$ 。

总结

把挂在交换机上的电脑也当作树节点，题目就变成标准树直径问题。两次 BFS 是无权树求直径的线性做法：第一次找到直径一端，第二次从该端出发量出直径长度。

时间限制： 1.0 秒

空间限制： 256 MB

问题描述

给定一个公司的网络，由 $n$ 台交换机和 $m$ 台终端电脑组成，交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置，编号为 $1$ 的交换机为根交换机，层级为 $1$ 。其他的交换机都连接到一台比自己上一层的交换机上，其层级为对应交换机的层级加 $1$ 。所有的终端电脑都直接连接到交换机上。

当信息在电脑、交换机之间传递时，每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问，电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n, m$ ，分别表示交换机的台数和终端电脑的台数。

第二行包含 $n - 1$ 个整数，分别表示第 $2, 3, \cdots, n$ 台交换机所连接的比自己上一层的交换机的编号。第 $i$ 台交换机所连接的上一层的交换机编号一定比自己的编号小。

第三行包含 $m$ 个整数，分别表示第 $1, 2, \cdots, m$ 台终端电脑所连接的交换机的编号。

输出格式

输出到标准输出。

输出一个整数，表示消息传递最多需要的步数。

input1

output1

样例 1 解释

样例的网络连接模式如下，其中圆圈表示交换机，方框表示电脑：

其中电脑 $1$ 与交换机 $4$ 之间的消息传递花费的时间最长，为 $4$ 个单位时间。

input2

output2

样例 2 解释

样例的网络连接模式如下：

其中电脑 $1$ 与电脑 $4$ 之间的消息传递花费的时间最长，为 $4$ 个单位时间。

评测用例规模与约定

前 $30\%$ 的评测用例满足： $n \le 5,~m \le 5$ 。

前 $50\%$ 的评测用例满足： $n \le 20,~m \le 20$ 。

前 $70\%$ 的评测用例满足： $n \le 100,~m \le 100$ 。

所有评测用例都满足： $1 \le n \le 10000,~1 \le m \le 10000$ 。

提示

Chap 11 图应用，树的最长通路（直径），习题 [6-9]。

习题解析上写的是“无向连通图的最长通路”，需要注意的是这个说法是完全错误的。一般图最长路径问题是 NP-Hard 问题，除非 P=NP，否则无法在多项式内解决该问题。

但是习题解析给出的 BFS 树做法对于求树的最长通路是适用的，除此之外还有树形 DP 的做法。

网络延时

目录

形式化题目

思路

关键观察

两次 BFS

代码

复杂度

总结