给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表，他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。
题目可以抽象为一个以0为根节点的树。
题目汽油数，可以转换为每一条边的需要的车辆数，因为最大容量固定，进而转化为每一条求每一条边经过了多少个人，进而转化为求每条边连接的邻接点的子树的节点个数。
每条边需要的车 = 每条边经过的人数/ 最大容量 上取整。
n/m上取整 = ( n + m -1 ) / n
每条边经过的人 = 该边 邻接点子树节点的个数。
可用使用dfs来解决：
dfs(i):以i为根节点子树的个数(包括根节点)。
int dfs(i):
res=0
for j in i 的邻接点列表：
res+=dfs(j)
return res+1
建图可以使用vector建立无向图。
class Solution {
private:
long long res = 0;
vector<vector<int>>g;
int seat;
int dfs(int i,int pre){
int cnt=0;
for(auto ne:g[i]){
if(ne==i||ne==pre) continue;
int t = dfs(ne,i);
cnt+=t;
res+=(t+seat-1)/seat;
}
return cnt+1;
}
public:
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
int n = roads.size();
g.resize(n+1);
seat=seats;
for(auto &e:roads){
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
dfs(0,-1);
return res;
}
};在使用dfs遍历邻接点的时候，如果相对每个子树都进行相同的操作，在for循环里面写。
