主題
題目連結：
題目意譯：
給定一棵由編號為 0 到 n - 1 的 n 個節點所組成的無向樹，其在節點上有些蘋果存在。你走過樹上的一條邊需要花一秒的時間?；貍鲝墓濣c 0 開始走到所有蘋果並採集，最後再回到節點 0 的最少所需時間。
無向樹的邊是以陣列 edges 給定，其中 edges[i] = [ai, bi] 代表著存在於一條邊連接著節點 ai 和節點 bi。此外，還有一個布林陣列 hasApple，其中 hasApple[i] = true 代表著節點 i 有著一顆蘋果；反之則無任何蘋果。
限制：
1 ≦ n ≦ 10 ^ 5
edges.length == n - 1
edges[i].length == 2
0 ≦ ai < bi ≦ n - 1
hasApple.length == n
範例測資：
範例 1：
輸入： n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
輸出： 8
解釋： 上圖代表著給定的樹，其中紅色的節點有著一顆蘋果。其中一條採集所有蘋果的最佳路徑為綠色箭頭。
範例 2：
輸入： n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
輸出： 6
解釋： 上圖代表著給定的樹，其中紅色的節點有著一顆蘋果。其中一條採集所有蘋果的最佳路徑為綠色箭頭。
範例 3：
輸入： n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
輸出： 0
解題思維：
從節點 0 遞迴求解即可。
假設現在位於節點 i，其子樹之根節點分別為 t1 、 t2 、……，而我們要先遞迴求解以 t1 、 t2 、…… 各自作為根節點的情況下採集對應的子樹中所有蘋果之最少所需時間。可以看到如果有子樹只有根節點有蘋果或是完全沒有蘋果存在，則所需時間為 0。
假設現在有某個以 tj 作為根節點的子樹之所需時間為 cj。如果 cj > 0，則我們需要從節點 i 走到 tj 的子樹去採集那些蘋果，因此所需時間將會加上 cj + 2（「+ 2」是因為要「走進子樹」以及「離開子樹」）；若 cj 為 0，但 hasApple[tj] 為真，代表我們還是需要走到 tj 來採集蘋果，因此所需時間加上 2；以上皆非的話，則不需走進該子樹，因此所需時間不變。
而節點 i 總體所需時間則是其子樹之所需時間按上述的方式推得。最後回傳節點 i 的所需時間到上一層遞迴即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
