题目描述

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads，其中 roads[i] = [a_i, b_i]，表示城市 a_i 和 b_i 之间有一条 双向路。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

样例

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。

输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出：7
解释：
- 代表 2 到达城市 3，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 5 直接到达首都，消耗 1 升汽油。
- 代表 6 到达城市 4，消耗 1 升汽油。
- 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。
最少消耗 7 升汽油。

输入：roads = [], seats = 1
输出：0
解释：没有代表需要从别的城市到达首都。

限制

• ·1 <= n <= 10^5`
• roads.length == n - 1
• roads[i].length == 2
• 0 <= a_i, b_i < n
• a_i != b_i
• roads 表示一棵合法的树。
• 1 <= seats <= 10^5

算法

(递归遍历) $O(n)$

1. 将无根树看做以 $0$ 节点为根的有根树，自底向上进行递归遍历。
2. 递归时，返回以当前节点 $u$ 为根的节点个数，以及将所有代表汇集到当前节点 $u$ 上时所消耗最少的汽油。
3. 消耗最少汽油的点在于将多位代表放到一辆车中移动，所以一条边的移动代价就是代表数除以座位数上取整。

时间复杂度

• 每个节点仅被遍历遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储图，递归的系统栈。

C++ 代码

#define LL long long

class Solution {
private:
    vector<vector<int>> graph;

    pair<int, LL> solve(int u, int fa, int seats) {
        int num = 1;
        LL cost = 0;

        for (int v : graph[u]) {
            if (v == fa)
                continue;

            auto p = solve(v, u, seats);
            num += p.first;
            cost += p.second + p.first / seats + bool(p.first % seats);
        }

        return make_pair(num, cost);
    }

public:
    LL minimumFuelCost(vector<vector<int>>& roads, int seats) {
        const int n = roads.size() + 1;

        graph.resize(n);

        for (const auto &e : roads) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        return solve(0, -1, seats).second;
    }
};