主題
題目連結：
題目意譯：
現在有一棵樹狀（即，一個連通且無環無向圖）國家交通網路，其由 n 座城市組成，其編號為 0 到 n - 1 並有恰好 n - 1 條道路。首都為城市 0。你被給定一個二維整數陣列 roads，其中 roads[i] = [ai, bi] 代表著城市 ai 和城市 bi 之間有一條雙向的道路連通彼此。
現在每一個城市的代表有一場會議。該會議位於首都。
現在每一座城市內有一台車。你被給定一整數 seats，其代表著每一台車中有的座位數。
一位代表可以使用他們城市內的車子來通勤或是在中途換車與另一位代表共乘。在兩座城市之間通行的成本為一公升的燃料。
回傳（所有代表）抵達首都最少所需燃料公升數。
（譯注：為了避免混淆，因故把原文沒有寫的「所有代表」加註了進去）
限制：
1 ≦ n ≦ 10 ^ 5
roads.length == n - 1
roads[i].length == 2
0 ≦ ai, bi < n
ai != bi
roads 代表著一棵合法的樹。
1 ≦ seats ≦ 10 ^ 5
範例測資：
範例 1：
輸入： roads = [[0,1],[0,2],[0,3]], seats = 5
輸出： 3
解釋：
- 1 號代表直接通勤至首都，並花費 1 公升的燃料。
- 2 號代表直接通勤至首都，並花費 1 公升的燃料。
- 3 號代表直接通勤至首都，並花費 1 公升的燃料。
其花費了最少量的 3 公升燃料。
可以證明 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 公升燃料。
可以證明 7 為最少所需的燃料公升數。
範例 3：
輸入： roads = [], seats = 1
輸出： 0
解釋： 沒有代表需要通勤到首都。
解題思維：
首先從輸入給定的 edges 建立出圖的鄰接表（Adjacency List，如這題）。這樣一來就方便從城市 0 遞迴下去（可以很簡單就找到其鄰居）。
可以觀察得到：當有兩位代表（或以上）可以共乘時，共乘會是最好的選擇（可以用反證法簡單證明，假設有其他種最佳解，接著我們就可以把該最佳解換成符合命題的條件。此時會發現這樣子的選擇不會比較差）。
接著我們直接遞迴求解即可：
假設我們知道城市 i 的所有鄰居（忽略其父母節點，也就是往城市 0（根節點）的方向） 的共乘情況。
再假設現在有一個鄰居為城市 j，而其共乘情況為 X 台完全坐滿的車子（也就是說這邊有 X × seats 位代表）以及一台未坐滿的車子，而上面有 Y 位代表。此時可以看到這些代表要從城市 j 跑到城市 i，其成本為 X + 1（如果 Y 實際上為 0，則成本為 X）。
因此我們可以直接統計城市 i 的所有鄰居，並知道這些鄰居各自到城市 i 的最小成本（如前所述，盡量共乘會是最好的選擇）。最後將這些鄰居的共乘情況加總簡化一下（能共乘的就共乘）便可以得到城市 i 自身的共乘情況。
由上我們可以看到這些代表會從葉節點一步一步地向根節點（即城市 0）靠近，而每移動一次就會算出一次最小成本。將這些最小成本加總即可得到所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
