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