J. Send the Fool Further! (easy) - 题解

比赛与标签

比赛: Helvetic Coding Contest 2017 online mirror (teams allowed, unrated) 标签: dfs and similar, graphs, trees 难度: *1400

题目到底在说什么喵~？

主人，这道题其实是一个很有趣的故事哦！简单来说，Heidi 的朋友们想跟她开个玩笑。从朋友 0（也就是 Jenny）开始，Heidi 会被派去给另一个朋友送信。收到信的朋友又会让她去给下一个朋友送信，就像一场寻宝游戏一样！

Heidi 很聪明，她知道自己不会被派去访问同一个人两次。朋友们之间的关系网构成了一棵树，每条路（边）都有一定的花费（权重）。

我们的任务就是，计算一下 Heidi 在这场“被捉弄”的旅途中，从朋友 0 出发，沿着某条路径一直走下去，最多会花费多少钱钱呢？也就是说，我们要找到从节点 0 出发，到树中其他任意一个节点的最长路径的长度，呐~

输入格式:

第一行是一个整数 n，代表朋友的总数。
接下来 n-1 行，每行有三个整数 u, v, c，表示朋友 u 和 v 之间直接认识，并且来往的花费是 c。

输出格式:

输出一个整数，表示 Heidi 可能花费的最大总金额。

解题思路大揭秘！

喵哈哈~ 这个问题听起来有点复杂，但其实只要看穿本质，就非常简单了喵！

题目说朋友关系网是一棵树，而且 Heidi 的旅程是一条不能重复访问节点的路径。这不就是树上的一条简单路径嘛？旅程的起点是固定的，就是朋友 0。

所以，我们的目标就变成了：计算在树中，从根节点 0 到其他所有节点的最长距离是多少。

想一想，要计算树上一个点到所有其他点的距离，最经典的方法是什么呀？当然是图的遍历算法啦！这里我们可以用深度优先搜索 (DFS) 或者广度优先搜索 (BFS)。DFS 写起来更简洁一些，我们就用 DFS 吧！

具体的思路是这样的说：

建图: 我们先把朋友关系用一个叫做邻接表的东西存起来。对于每个朋友 u，我们都记录下所有和他直接相连的朋友 v 以及他们之间的花费 c。因为是朋友关系是双向的，所以 u 到 v 和 v 到 u 都要记录哦。
定义距离数组: 我们需要一个数组 dist，dist[i] 用来存放从起点 0 到朋友 i 的总花费。一开始，我们只知道 dist[0] = 0，其他都还不清楚。
开始DFS: 我们从节点 0 开始进行深度优先搜索。
- 我们定义一个函数 dfs(u, parent)，表示当前访问到了节点 u，u 是从 parent 节点过来的。parent 这个参数很重要哦，它可以防止我们走回头路，保证我们一直在往下探索新的路径。
- 当我们从节点 u 走到它的一个邻居 v 时（当然 v 不能是 parent），从 0 到 v 的距离就是从 0 到 u 的距离，再加上 u 和 v 之间的花费。也就是：dist[v] = dist[u] + c。
- 然后，我们再从 v 继续往下搜索，调用 dfs(v, u)。
找到最大值: 当 DFS 遍历完所有可以从 0 到达的节点后，dist 数组里就存满了从 0 到每个节点的路径总花费啦。我们只需要找到这个数组里的最大值，就是 Heidi 可能被“骗”走的最大金额了！

是不是很简单呢？就像小猫咪顺着毛线球的线头一路追寻，直到找到线的尽头一样喵~

AC代码奉上！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 用邻接表来存储我们的树，喵~
// 每个节点存储一个pair<int, int>的列表，分别代表邻居节点和边权（花费）
vector<vector<pair<int, int>>> adj;

// dist[i] 用来存储从起点0到节点i的总花费
vector<int> dist;

// 深度优先搜索函数，喵呜~
// u: 当前访问的节点
// parent: u的父节点，用来防止走回头路
void dfs(int u, int parent) {
    // 遍历当前节点u的所有邻居
    for (auto edge : adj[u]) {
        int v = edge.first;  // 邻居节点
        int c = edge.second; // 到邻居的花费

        // 如果邻居是父节点，就跳过，不然就绕回去了！
        if (v == parent) continue;

        // 更新从起点到邻居v的距离
        // 距离v = 距离u + u到v的花费
        dist[v] = dist[u] + c;

        // 从邻居v继续往下探索！
        dfs(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false); // 加速输入输出，跑得更快喵！
    cin.tie(NULL);

    int n;
    cin >> n;

    // 根据朋友数量n，初始化邻接表和距离数组
    adj.resize(n);
    dist.resize(n, 0);

    // 读取n-1条边，构建我们的朋友关系树
    for (int i = 0; i < n - 1; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        // 朋友关系是双向的，所以要加两条边
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    // 起点是0，所以它到自己的距离当然是0啦
    dist[0] = 0;
    // 从节点0开始DFS，-1表示0没有父节点
    dfs(0, -1);

    // 遍历结束后，dist数组里最大的那个值就是答案啦！
    // 使用 *max_element 可以方便地找到最大值
    int ans = *max_element(dist.begin(), dist.end());
    cout << ans << endl;

    return 0;
}

复杂度分析喵~

时间复杂度: O(N) 的说。我们的 DFS 算法会访问每个节点（朋友）一次，也会遍历每条边（朋友关系）一次。在树中，有 N 个节点和 N-1 条边。所以 DFS 的时间复杂度是 O(N + (N-1))，也就是 O(N)。最后找最大值的 max_element 也是 O(N) 的。总的来说，就是 O(N) 啦，非常高效！
空间复杂度: O(N) 的说。我们用邻接表 adj 来存图，它需要 O(N) 的空间。dist 数组也需要 O(N) 的空间。DFS 递归时，系统调用栈的深度在最坏情况下（一条链）也是 O(N)。所以总的空间复杂度是 O(N) 呢。

知识点与总结

这道题虽然是图论背景，但其实核心非常直接，是对基础算法的考察，主人要好好掌握哦！

问题转化: 关键在于把故事背景转化为一个清晰的算法问题：求树上固定根节点到所有其他节点的最长路径。
树的遍历: DFS 是解决这类树上路径问题的强大工具。通过记录父节点来避免回溯，是处理无向图表示的树时的一个常用技巧。
数据结构: 邻接表是存储稀疏图（比如树）的标准且高效的方式。
注意起点: 这道题和求“树的直径”不一样哦！树的直径是求树中任意两点间的最长路径，通常需要两次DFS或BFS。而这道题的起点是固定的节点 0，所以一次DFS就足够啦！

希望这篇题解能帮助到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！加油，你一定可以的！

J. Send the Fool Further! (easy) - 题解 ​

比赛与标签 ​

题目到底在说什么喵~？ ​

解题思路大揭秘！ ​

AC代码奉上！ ​

复杂度分析喵~ ​

知识点与总结 ​