给出一棵树的边集，以及车的seat数量，除了根节点0外的每个节点有一位乘客要去根节点，汽车每开一条边消耗一单位汽油，问至少花费多少汽油可以运送所有乘客去根节点
DFS，记录每个节点的所有儿子节点的数量，然后计算加上当前节点的一位乘客需要几辆车，更新从该节点到上一个节点的汽油用量
1 #2477
2 #Runtime: 1735 ms (Beats 64.71%)
3 #Memory: 168.2 MB (Beats 11.76%)
4
5 class Solution(object):
6 def minimumFuelCost(self, roads, seats):
7 """
8 :type roads: List[List[int]]
9 :type seats: int
10 :rtype: int
11 """
12 vis = [0] * (len(roads) + 1)
13 tr = defaultdict(list)
14 for a, b in roads:
15 tr[a].append(b)
16 tr[b].append(a)
17
18 def DFS(node):
19 vis[node] = 1
20 cnt = 1
21 for x in tr[node]:
22 if not vis[x]:
23 cnt += DFS(x)
24 if node:
25 self.ans += cnt // seats
26 if cnt % seats:
27 self.ans += 1
28 return cnt
29
30 self.ans = 0
31 DFS(0)
32 return self.ans