力扣：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
解释：没有代表需要从别的城市到达首都。

思路：

说有一个树结构，节点代表城市，首都在 0 号节点，每条路是双向的。每个城市有一个人，他们要开车到首都，车的座位数是 seats，每辆车每行驶 1 单位距离消耗 1 单位油，求最少总油耗。

首先，我需要分析这个代码的思路。代码里用了两个邻接表，a 是有向的（只存子节点），b 是无向的。build 函数应该是把无向图转换成以 0 为根的有向树，确定父节点和子节点的关系，避免循环。

然后看 fun 函数，这应该是一个递归函数，后序遍历树。每个节点返回两个值：sum 是该节点及其所有子节点的总人数（因为每个人都要往父节点移动），w 是这些人移动到当前节点所需的总油耗。

对于叶子节点，sum 是 1（只有自己），w 是 0（不需要移动到子节点，因为它没有子节点）。对于非叶子节点，遍历所有子节点，累加子节点的 sum 得到总人数（加上自己就是当前节点的 sum），而油耗方面，每个子节点的人需要移动到当前节点，所以要加上子节点的 w（子节点内部的油耗），再加上子节点的人移动到当前节点的油耗。移动的油耗计算是（子节点人数 + seats - 1）/seats，这其实是向上取整，因为每辆车最多坐 seats 人，需要的车数就是向上取整后的结果，每辆车走 1 段路，所以总油耗就是车数。

整个过程是从叶子节点往上计算，最后根节点（0 号）的 w 就是总油耗，因为所有人都已经移动到根节点了。

AC代码：

C++版本：

class Solution {
public:static const int N = 1e5 + 10;vector<int> a[N];// 有向邻接表，只存储子节点vector<int> b[N];// 无向邻接表，存储所有边bool flag[N];typedef struct {long long w;// 汇聚到当前结点的最少油耗long long sum;// 所有子节点向当前结点汇聚，该节点（包含）上一共有多少人}Node;long long minimumFuelCost(vector<vector<int>>& roads, int seats) {if (roads.empty()) {return 0;}memset(flag, 0, sizeof flag);for (int i = 0;i < roads.size();i++) {//无向邻接表存图int u = roads[i][0];int v = roads[i][1];b[u].push_back(v);b[v].push_back(u);}build(0, 0);//无向邻接表转有向return fun(0, seats).w;}Node fun(int x, int seats) {Node t;if (a[x].empty()) {//到达叶子结点t.sum = 1;t.w = 0;return t;}long long sum = 0;long long w = 0;for (int i = 0;i < a[x].size();i++) {Node k = fun(a[x][i], seats);sum += k.sum;w += k.w + (k.sum + seats - 1) / seats;}t.sum = sum + 1;t.w = w;return t;}void build(int idx, int fa) {for (auto it : b[idx]) {if (it == fa) {continue;}else {a[idx].push_back(it);}}for (auto it : a[idx]) {build(it, idx);}}
};

java版本：

class Solution {class Node{long w;long sum;}static final int N=100010;public ArrayList<Integer>[] a=new ArrayList[N];public ArrayList<Integer>[] b=new ArrayList[N];public long minimumFuelCost(int[][] roads, int seats) {if(roads==null||roads.length==0){return 0;}for (int i = 0; i < N; i++) {a[i]=new ArrayList<>();b[i]=new ArrayList<>();}for(int[] i:roads){int u=i[0];int v=i[1];b[v].add(u);b[u].add(v);}build(0,0);return fun(0,seats).w;}Node fun(int x,int seats){Node t=new Node();t.sum=1;t.w=0;if(a[x].size()==0){return t;}for (int i = 0; i < a[x].size(); i++) {Node k=fun(a[x].get(i),seats);t.sum+=k.sum;t.w+=k.w+(k.sum+seats-1)/seats;}return t;}public void build(int idx,int fa){for(int i:b[idx]){if(i==fa){continue;}else{a[idx].add(i);}}for(int i:a[idx]){build(i,idx);}}
}