如何以最低油费抵达首都？—— LeetCode每日一题第2477题解析

该题考察多叉树的遍历。题目中的题可能会让人有些迷糊，画成树的形式就容易理解的多，本题的问题有以下几点可以帮助理解：

1. 从各个节点送人到首都，等价于从首都把人送到各个节点，既然是从首都出发到各个节点，那么就可以采用dfs或bfs。
2. 将油耗分段计算。从一个节点到它的父节点（上一个子树的根节点），假设cur节点后的所有人都已经到了cur节点，且当前有curnum个人，那么总共需要(curnum + seats - 1) / seats的油将这些人送到father节点。那么当前所需要知道的是，在cur节点，总共会聚集多少人。而聚集多少人是由子树的节点数量决定的，那么问题就转换为了计算子树中有多少个节点。
3. 在图中通常需要设置visit数组来记录哪些节点被访问过了，以避免重复访问。但是本题给出的是多叉树，因此，处于cur节点的时候，唯一可能重复访问的只有父节点。因此在遍历cur节点联通的节点时，只需判断下一个节点是不是father节点，若是则跳过。

class Solution {
public:
    vector<vector<int>> g;  // 邻接链表
    long long int ans = 0;
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        g = vector<vector<int>>(n);
        for(auto & r : roads){  // 双向图，需要在两个顶点上都加入邻接点
            g[r[0]].push_back(r[1]);
            g[r[1]].push_back(r[0]);
        }
        dfs(0, 0, seats);
        return ans;
    }

    int dfs(int cur, int father, int seats){  // cur是当前所在的节点， father是上一个来cur的节点； 返回从cur到father有多少人。
        int curnum = 1;  // 记录当前节点有多少人要去father节点，初始时只有这个节点的那个人
        for(int i = 0; i < g[cur].size(); ++i){
            int v = g[cur][i];
            if(v == father)continue;  // 是从这个节点过来的，所以这个节点就不用遍历了。
            int t = dfs(v, cur, seats);  // 记录从v来的人数
            ans += ((t + seats - 1) / seats);  // 从v到cur要花的油
            curnum += t;  // 把子树节点的人聚集起来。
        }
        return curnum;  // 一班车发到father节点
    }
};