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