本文共 1950 字，大约阅读时间需要 6 分钟。

树结构中的节点间最大距离计算

本文将详细阐述一种高效的算法，用于计算一棵树中任意节点到其他所有节点的最大距离。

算法概述

我们采用两阶段深度优先搜索预处理的方法，来确定每个节点到树上所有节点的最大距离。一种关键 challenge是如何高效地处理跳跃到父节点的情况。

树的表示和初始化

树的结构采用邻接表形式表示，具体使用以下数组：

• e[i]：子节点的信息。
• h[i]：子节点指针。
• w[i]：边的权重。

遍历过程中使用以下辅助数组：

• d1[i]：当前遍历路径中到下一个节点的最大距离。
• d2[i]：当前节点到其他所有节点的最大距离。
• up[i]：节点的跳跃父节点。
• p1[i]：用于道路标记的节点。

第一阶段：DFS遍历

首先进行第一次DFS遍历，从根节点（假设为节点1）开始，逐层遍历所有节点。对于每个节点u，我们计算其到下一个节点j的最大距离，并在完成遍历后记录每个节点的最大距离值。

具体实现步骤如下：

void dfs(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u); // 递归遍历子节点
        if (d1[j] + w[i] > d1[u]) {
            d2[u] = d1[u];
            d1[u] = d1[j] + w[i];
            p1[u] = j;
        } else if (d1[j] + w[i] > d2[u]) {
            d2[u] = d1[j] + w[i];
        }
    }
}

第二阶段：DFS2遍历

第二阶段DFS2遍历用于解决“溢出”问题。当u节点的跳跃路径中出现更长的路径时，我们需要更新其父节点的最大距离。

具体实现步骤如下：

void dfs2(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        // 更新j节点的最大距离
        if (d1[u] + w[i] > up[j]) {
            up[j] = d1[u] + w[i];
            if (p1[u] != j) {
                dfs2(j, u); // 继续递归遍历
            }
        }
    }
}

主函数逻辑

主函数部分负责读取输入数据并初始化相关数组。具体实现如下：

int main() {
    while (cin >> n) {
        // 初始化
        memset(h, -1, sizeof(h));
        idx = 0;
        for (int i = 0; i <= n; i++) {
            d1[i] = 0;
            d2[i] = 0;
            up[i] = 0;
        }
        // 读取输入并构建树
        for (int i = 2; i <= n; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
            add(b, a, c);
        }
        // 进行两次DFS遍历
        dfs(1, -1);
        dfs2(1, -1);
        // 输出结果
        for (int i = 1; i <= n; i++) {
            cout << d1[i] << ' ' << d2[i] << '\n';
        }
    }
}

结果输出

主函数完成两次DFS遍历后，逐个输出每个节点的最大距离（d1[i]）和次大距离（d2[i]），得到每个节点到树上其他所有节点的距离信息。

总结

通过两阶段DFS遍历，我们成功地解决了树结构中的节点间跳跃问题，确保每个节点的最大距离计算准确高效。这一方法在处理大规模树结构时表现优异，是解决类似问题的经典方案。