到达首都的最少油耗 图解题解

这道题到底在问什么

输入

roads=[[0,1],[0,2],[0,3]], seats=5

输出

3

输入

roads=[], seats=1

输出

0

最优解：一步一步想明白

1. 3记牢这一句:每条路的车数,等于这条路下面那棵子树的人数,除以座位数再向上取整。为什么可以一条边一条边地独立算,因为子树里的人不管怎么拼,最终都得挤过这唯一一条通向首都的路。下面把首都放在最上面,一层一层往下把人数数清。
2. 4目标:总油耗最少先把整棵树摆出来。城市 0 是首都,画在最上面,另外 7 座城顺着道路挂在它下面,一共 8 座城,每座城住着一位代表。每辆车坐 2 人,也就是 seats 等于 2。首都自己的代表已经在会场,不烧油;其余 7 位都要往上开。我们从最底下的城开始,一层层把子树里的人数数清,再折算每条路要几辆车。
3. 5根 = 首都 0从首都 0 出发做后序搜索。后序的意思是先把孩子那边全部数完,再回过头结算自己。首都下面挂着城市 1 和城市 2 两大分支,先钻进城市 1 那一支,一路往下探到最底端。
4. 6访问城市 1顺着道路往下走,来到城市 1。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
5. 7城市 3 子树 = 1城市 3 是这条线的末端,底下没有别的城了。它这棵子树里就它自己一位代表,人数记 1。把它标成绿色,表示这一块已经数清,可以把这个 1 交还给它的父亲了。
6. 81 人过路, 开 1 车城市 3 这一支数好了,子树里一共 1 位代表。这些人都要挤过 城市 3 到城市 1 这一条路开向首都。每辆车坐 2 人:1 位代表还坐不满一车, 但也得开 1 辆车。这条路就耗 1 升油,累计油耗到 1 升。同时把这 1 位代表并进城市 1 的子树一起往上带。
7. 9访问城市 4顺着道路往下走,来到城市 4。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
8. 10城市 6 子树 = 1城市 6 是这条线的末端,底下没有别的城了。它这棵子树里就它自己一位代表,人数记 1。把它标成绿色,表示这一块已经数清,可以把这个 1 交还给它的父亲了。
9. 111 人过路, 开 1 车城市 6 这一支数好了,子树里一共 1 位代表。这些人都要挤过 城市 6 到城市 4 这一条路开向首都。每辆车坐 2 人:1 位代表还坐不满一车, 但也得开 1 辆车。这条路就耗 1 升油,累计油耗到 2 升。同时把这 1 位代表并进城市 4 的子树一起往上带。
10. 12城市 4 子树 = 2城市 4 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 2 位代表。城市 4 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 2 个人去折算要开几辆车。
11. 132 人过路, 开 1 车城市 4 这一支数好了,子树里一共 2 位代表。这些人都要挤过 城市 4 到城市 1 这一条路开向首都。每辆车坐 2 人:2 位代表正好坐满 1 辆车。这条路就耗 1 升油,累计油耗到 3 升。同时把这 2 位代表并进城市 1 的子树一起往上带。
12. 14城市 1 子树 = 4城市 1 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 4 位代表。城市 1 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 4 个人去折算要开几辆车。
13. 154 人过路, 开 2 车城市 1 这一支数好了,子树里一共 4 位代表。这些人都要挤过 城市 1 到城市 0 这一条路开向首都。每辆车坐 2 人:4 位代表正好装满 2 辆车, 一个空座都不剩。这条路就耗 2 升油,累计油耗到 5 升。同时把这 4 位代表并进城市 0 的子树一起往上带。
14. 16访问城市 2顺着道路往下走,来到城市 2。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
15. 17访问城市 5顺着道路往下走,来到城市 5。它底下还挂着更下级的城,别急着给它算账,先继续深入,把它子树里到底有多少位代表数清楚,再回来处理它头顶这条路。
16. 18城市 7 子树 = 1城市 7 是这条线的末端,底下没有别的城了。它这棵子树里就它自己一位代表,人数记 1。把它标成绿色,表示这一块已经数清,可以把这个 1 交还给它的父亲了。
17. 191 人过路, 开 1 车城市 7 这一支数好了,子树里一共 1 位代表。这些人都要挤过 城市 7 到城市 5 这一条路开向首都。每辆车坐 2 人:1 位代表还坐不满一车, 但也得开 1 辆车。这条路就耗 1 升油,累计油耗到 6 升。同时把这 1 位代表并进城市 5 的子树一起往上带。
18. 20城市 5 子树 = 2城市 5 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 2 位代表。城市 5 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 2 个人去折算要开几辆车。
19. 212 人过路, 开 1 车城市 5 这一支数好了,子树里一共 2 位代表。这些人都要挤过 城市 5 到城市 2 这一条路开向首都。每辆车坐 2 人:2 位代表正好坐满 1 辆车。这条路就耗 1 升油,累计油耗到 7 升。同时把这 2 位代表并进城市 2 的子树一起往上带。
20. 22城市 2 子树 = 3城市 2 的下级都收拢完了,把它自己那位代表也算上,这棵子树一共 3 位代表。城市 2 标绿,表示它这一块彻底数清。接下来就轮到它头顶那条通往上级的路,用这 3 个人去折算要开几辆车。
21. 233 人过路, 开 2 车城市 2 这一支数好了,子树里一共 3 位代表。这些人都要挤过 城市 2 到城市 0 这一条路开向首都。每辆车坐 2 人:3 位代表, 先装满 1 辆车, 还剩 1 人得再开 1 辆, 一共 2 辆车。这条路就耗 2 升油,累计油耗到 9 升。同时把这 3 位代表并进城市 0 的子树一起往上带。
22. 24答案 = 9回到首都 0。它的两大分支都汇总完了:城市 1 那支的 4 人账已折成 2 升油,城市 2 那支的 3 人账折成 2 升油。连同下面各条小路,所有边的油耗加起来一共 9 升。首都自己的代表本就在会场,不用开车,不产生油耗。这 9 升就是最终答案。
23. 25总油耗 = 9 升回头看一眼七条路各烧了多少油。靠近末端的五条路,人数都不超过 2,各开 1 辆车、各 1 升;剩下两条汇进首都的大路:城市 1 到首都 4 个人正好坐满 2 车,是 2 升;城市 2 到首都 3 个人得开 2 车,末车坐不满也算,还是 2 升。五个 1 加两个 2,正好 9 升。核心始终一句:每条路的车数,是它下面子树人数除以座位再向上取整。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        def dfs(a: int, fa: int) -> int:
            nonlocal ans
            sz = 1
            for b in g[a]:
                if b != fa:
                    t = dfs(b, a)
                    ans += ceil(t / seats)
                    sz += t
            return sz

        g = defaultdict(list)
        for a, b in roads:
            g[a].append(b)
            g[b].append(a)
        ans = 0
        dfs(0, -1)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<int> g[n];
        for (auto& e : roads) {
            int a = e[0], b = e[1];
            g[a].emplace_back(b);
            g[b].emplace_back(a);
        }
        long long ans = 0;
        function<int(int, int)> dfs = [&](int a, int fa) {
            int sz = 1;
            for (int b : g[a]) {
                if (b != fa) {
                    int t = dfs(b, a);
                    ans += (t + seats - 1) / seats;
                    sz += t;
                }
            }
            return sz;
        };
        dfs(0, -1);
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private List<Integer>[] g;
    private int seats;
    private long ans;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        this.seats = seats;
        for (int[] e : roads) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        dfs(0, -1);
        return ans;
    }

    private int dfs(int a, int fa) {
        int sz = 1;
        for (int b : g[a]) {
            if (b != fa) {
                int t = dfs(b, a);
                ans += (t + seats - 1) / seats;
                sz += t;
            }
        }
        return sz;
    }
}

复杂度

面试官可能追问