給出一棵樹的邊集，以及車的seat數量，除了根節(jié)點0外的每個節(jié)點有一位乘客要去根節(jié)點，汽車每開一條邊消耗一單位汽油，問至少花費多少汽油可以運送所有乘客去根節(jié)點
DFS，記錄每個節(jié)點的所有兒子節(jié)點的數量，然后計算加上當前節(jié)點的一位乘客需要幾輛車，更新從該節(jié)點到上一個節(jié)點的汽油用量
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