Question

2477. 到达首都的最少油耗

English Version

题目描述

给你一棵 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

解法

方法一：贪心 + DFS

根据题目描述，我们可以发现，所有车只会往首都（节点 $0$）开。

假设有一个节点 $a$，它的下一个节点为 $b$，节点 $a$ 需要经过节点 $b$ 才能到达首都。为了使得节点 $a$ 的车辆（油耗）尽可能少，我们应该贪心地让节点 $a$ 的子节点先汇聚到节点 $a$，然后按照座位数 $seats$ 分配车辆，那么到达节点 $b$ 需要的最少车辆（油耗）就是 $\lceil \frac{sz}{seats} \rceil$。其中 $sz$ 表示以节点 $a$ 为根的子树的节点数。

我们从节点 $0$ 开始进行深度优先搜索，用一个变量 $sz$ 统计以当前节点为根节点的子树的节点数。初始时 $sz = 1$，表示当前节点本身。然后我们遍历当前节点的所有子节点，对于每个子节点 $b$，我们递归地计算以 $b$ 为根节点的子树的节点数 $t$，并将 $t$ 累加到 $sz$ 上，然后我们将 $\lceil \frac{t}{seats} \rceil$ 累加到答案上。最后返回 $sz$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为节点数。

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

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

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

func minimumFuelCost(roads [][]int, seats int) (ans int64) {
  n := len(roads) + 1
  g := make([][]int, n)
  for _, e := range roads {
    a, b := e[0], e[1]
    g[a] = append(g[a], b)
    g[b] = append(g[b], a)
  }
  var dfs func(int, int) int
  dfs = func(a, fa int) int {
    sz := 1
    for _, b := range g[a] {
      if b != fa {
        t := dfs(b, a)
        ans += int64((t + seats - 1) / seats)
        sz += t
      }
    }
    return sz
  }
  dfs(0, -1)
  return
}

function minimumFuelCost(roads: number[][], seats: number): number {
  const n = roads.length + 1;
  const g: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of roads) {
    g[a].push(b);
    g[b].push(a);
  }
  let ans = 0;
  const dfs = (a: number, fa: number): number => {
    let sz = 1;
    for (const b of g[a]) {
      if (b !== fa) {
        const t = dfs(b, a);
        ans += Math.ceil(t / seats);
        sz += t;
      }
    }
    return sz;
  };
  dfs(0, -1);
  return ans;
}

impl Solution {
  pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
    let n = roads.len() + 1;
    let mut g: Vec<Vec<usize>> = vec![vec![]; n];
    for road in roads.iter() {
      let a = road[0] as usize;
      let b = road[1] as usize;
      g[a].push(b);
      g[b].push(a);
    }
    let mut ans = 0;
    fn dfs(a: usize, fa: i32, g: &Vec<Vec<usize>>, ans: &mut i64, seats: i32) -> i32 {
      let mut sz = 1;
      for &b in g[a].iter() {
        if (b as i32) != fa {
          let t = dfs(b, a as i32, g, ans, seats);
          *ans += ((t + seats - 1) / seats) as i64;
          sz += t;
        }
      }
      sz
    }
    dfs(0, -1, &g, &mut ans, seats);
    ans
  }
}