每日一题 --- 2477. 到达首都的最少油耗

链式前向星解法?

核心点是我dfs两次，第一次是求出每个节点的叶子节点有多少个？

因为我们可以看做从当前节点出发到当前节点的根节点的话，那么需要知道当前节点叶子节点个数，也就是我们让当前节点的叶子结点（代表）先来到当前节点集合，那么这就是一个子问题

那么对于子问题解法，我们可以记忆化搜索或者利用递归特性

本题采用记忆化搜索解法来解决

f[i]，代表最终会有几个人到i点集合

dp[i]，代表到i点集训最少需要消耗多少油

class Solution {
public:
    int h[510000], ne[510000], e[510000], idx;
    bool st[110000] = {0};
    long long dp[110000] = {0};

    long long dfs1(int u, int seats, vector<long long>& f) {
        st[u] = true;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int b = e[i];
            if (st[b]) continue;

            long long cnt = dfs1(b, seats, f);
            f[u] = f[u] + cnt;
        }
        return f[u];
    }

    long long dfs2(int u, int seats, vector<long long>& f) {
        st[u] = true;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int b = e[i];
            if (st[b]) continue;

            dfs2(b, seats, f);
            dp[u] = dp[u] + (f[b] / seats) + ((f[b] % seats == 0) ? 0 : 1) + dp[b];
        }

        return dp[u];
    }

    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }

    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        vector<long long> f(110000, 1);
        f[0] = 0;
        memset(h, -1, sizeof(h));

        for (auto& e : roads) {
            int a = e[0];
            int b = e[1];
            add(a, b), add(b, a);
        }

        memset(st, 0, sizeof(st));
        dfs1(0, seats, f);

        memset(st, 0, sizeof(st));
        dfs2(0, seats, f);

        return dp[0];
    }
};