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

把所有代表送到首都，最少烧多少油

n 座城连成一棵树，城市 0 是首都，roads 里每项是一条双向路。每座城住一位代表要赶去首都，一辆车坐 seats 人，相邻两城之间开一趟耗 1 升油，路上能拼车。求送全部代表到首都最少烧多少油。题面例子 roads=[[0,1],[0,2],[0,3]]、seats=5，答案 3；另一组 roads=[]、seats=1，只有首都、没人出行，答案 0。

让每人各开一辆直奔首都，亏在哪

题面准了拼车，能省多少？要排一张全局拼车表——谁半路捎上谁、在哪汇合——十万位代表的组合根本枚举不完。让每人各开一辆直达倒好算，可相邻本能合坐的代表却各烧各的油，越靠近首都越亏。

每条路都非过不可，于是各算各的

树上每座城通往首都的路是唯一的。盯住某一条边，它下面那棵子树里的所有代表不管怎么拼车，最后都得挤过这唯一一条边往首都走。过边人数固定、又非走不可，把车尽量坐满就是最优：车数 = 子树人数 ÷ 座位数 再向上取整。每条边彼此不牵扯，各自算完加起来就是全局最少油耗。

怎么把子树人数数清？从首都 0 做后序遍历，也就是先把每个孩子子树数清，再算上自己这一位。roads 是双向路，记成来回都能走，一趟 DFS 既往下钻、又把人数捎回来。

DFS 每到一座城，返回什么、累加什么

递归写成 dfs(a, fa)，a 是当前城、fa 是父亲。先给 sz 记 1，算上 a 自己那位代表。再遍历 a 的邻居 b：碰到 fa 就跳过，免得走回父亲；碰到孩子 b，先递归 t = dfs(b, a) 拿到子树人数，给 a 到 b 这条边结账，ans 加上 t ÷ seats 向上取整的车数，再把 t 并进 sz。走完返回 sz。

返回值 sz 只往父亲传子树人数，累加器 ans 一路收每条边的油耗。首都 0 头顶没有上行边，dfs(0, -1) 的返回值只是收尾，不给根算过路油。

拿题面 [[0,1],[0,2],[0,3]] 顺着递归跑一趟

roads=[[0,1],[0,2],[0,3]]、seats=5。建图后首都 0 连着末端城 1、城 2、城 3。dfs(0, -1) 依次钻进三个孩子：dfs(1, 0) 里城 1 除父亲外没邻居，sz=1 返回；回到 0 给边 0-1 结账，1 ÷ 5 向上取整 1 辆，ans=1。城 2、城 3 同样各返回 1、各加 1 辆，ans 走到 3。三人虽一辆五座车坐得下，可分处三条路各必开一辆，所以 3 升不是 1 升。

边界那组 roads=[]、seats=1：一条边都没有，0 没邻居直接返回，ans 没加，答案 0。

座位为 1 的深链，会把 int 撑爆

复杂度上，建邻接表遍历 n−1 条边、后序 DFS 每座城每条边只看常数次，时间 O(n)；邻接表加上递归栈最坏在链形树深达 n 层，空间也是 O(n)。

几处最容易栽：车数一律向上取整，坐不满也得再开一辆，向下取整会漏人；ans 必须用 long，座位为 1、树深成链时靠近根的边人数极大，车数逐段累加能到十亿量级、int 会溢出；遍历邻居忘跳过 fa 就会折回父亲、无限递归；给根补上行边的车则多算了油。

Python

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

C++

#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;
    }
};

Java

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;
    }
}