网络延时 第四次CCF-CSP计算机软件能力认证

就是求树的直径:

思路：函数代表当前根节点的最长距离 然后遍历保存当前树的所有孩子的最长距离 和次长距离 如果是叶子节点就返回0

在每次获得每个节点的次长距离和最长距离就更新全局直径 最后获得最长距离

Ac代码:

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

const int MAXN = 20005;          // n + m ≤ 2 × 10⁴

struct Node {
    vector<int> child;           // 下挂节点
    int parent = 0;              // 可选：上级交换机
} tree[MAXN];

int n, m;
int diameter_len = 0;            // 全局最长路径（边数）

/*
 * dfs(u) 返回：以 u 为根向“最深叶子”走下去的最大深度（边数）
 * 同时在回溯阶段用两条最大的儿子深度 candidate1、candidate2
 * 来更新经过 u 的最长路径，从而维护全局直径 diameter_len
 */
int dfs(int u)
{
    int first = 0, second = 0;   // 当前结点两条最大下行深度

    for (int v : tree[u].child)
    {
        int d = dfs(v) + 1;      // +1 把边 u→v 计入深度
        if (d > first) {
            second = first;
            first = d;
        }
        else if (d > second) {
            second = d;
        }
    }

    diameter_len = max(diameter_len, first + second);  // 经过 u 的最长“弯”路径
    return first;                                      // 向上传递最大深度
}

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

    if (!(cin >> n >> m)) return 0;


    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        tree[i].parent = p;
        tree[p].child.push_back(i);
    }

    for (int i = 1; i <= m; ++i) {
        int p; cin >> p;           // 父交换机编号
        int id = n + i;
        tree[id].parent = p;
        tree[p].child.push_back(id);
    }

    dfs(1);                        // 根为 1
    cout << diameter_len << '\n';  // 最长消息转发路径（边数）

    return 0;
}