2477-到达首都的最少油耗

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

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

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

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

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

示例 1：

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

示例 2：

**输入：** 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 升汽油。

示例 3：

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

提示：

• 1 <= n <= 105
• roads.length == n - 1
• roads[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• roads 表示一棵合法的树。
• 1 <= seats <= 105

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

---

考虑每条边上至少需要多少辆车。

以 0 为根，设子树 x 的大小为 size，那么它到它父节点这条边的「流量」是 size，那么就至少需要 \left\lceil\dfrac{\textit{size} }{\textit{seats} }\right\rceil 辆车。

累加除了 x=0 以外的值，就是答案。

[sol1-Python3]

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        ans = 0
        g = [[] for _ in range(len(roads) + 1)]
        for x, y in roads:
            g[x].append(y)
            g[y].append(x)
        def dfs(x: int, fa: int) -> int:
            size = 1
            for y in g[x]:
                if y != fa:
                    size += dfs(y, x)
            if x:
                nonlocal ans
                ans += (size + seats - 1) // seats
            return size
        dfs(0, -1)
        return ans

[sol1-Go]

func minimumFuelCost(roads [][]int, seats int) int64 {
	ans := 0
	g := make([][]int, len(roads)+1)
	for _, e := range roads {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}
	var dfs func(int, int) int
	dfs = func(x, fa int) int {
		size := 1
		for _, y := range g[x] {
			if y != fa {
				size += dfs(y, x)
			}
		}
		if x > 0 {
			ans += (size + seats - 1) / seats
		}
		return size
	}
	dfs(0, -1)
	return int64(ans)
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为 roads 的长度。
• 空间复杂度：O(n)。