主題
題目連結：
題目意譯：
現在存在著一個無向且一開始無根的樹，其有 n 個編號為 0 到 n - 1 的節點。你被給定整數 n 以及一個長度為 n - 1 的二維陣列 edges，其中 edges = [ai, bi] 代表著在樹中節點 ai 和節點 bi 之間有一條邊。
每一個節點有一個對應的價格。你被給定一個整數陣列 price，其中 price[i] 為節點 i 的價格。
一個給定的路徑之路徑和為在路徑上的所有節點之價格總和。
該樹可以根據你的選擇來以任何節點作為根節點。選擇根節點的成本為從該根節點出發的所有路徑中最大價格和與最小價格和之差。
回傳在所有可能的根節點選擇中的最大成本。
限制：
1 ≦ n ≦ 10 ^ 5
edges.length == n - 1
0 ≦ ai, bi ≦ n - 1
edges 代表著一棵合法的樹。
price.length == n
1 ≦ price[i] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
輸出： 24
解釋： 上圖代表著以節點 2 作為根節點。第一部份（紅色部分）顯示了有著最大價格和的路徑。第二部分（藍色部分）顯示了有著最小價格和的路徑。
- 第一部份包含著節點 [2,1,3,4]：價格為 [7,8,6,10]，而價格總和為 31。
- 第一部份包含著節點 [2]：價格為 [7]。
價格和的最大值與最小值之差為 24。可以證明 24 是最大的成本。
範例 2：
輸入： n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
輸出： 2
解釋： 上圖代表著以節點 0 作為根節點。第一部份（紅色部分）顯示了有著最大價格和的路徑。第二部分（藍色部分）顯示了有著最小價格和的路徑。
- 第一部份包含著節點 [0,1,2]：價格為 [1,1,1]，而價格總和為 3。
- 第一部份包含著節點 [0]：價格為 [1]。
價格和的最大值與最小值之差為 2。可以證明 2 是最大的成本。
解題思維：
假設定義出「樹直徑」的兩個節點為 L 和 R，也就是說 L 到 R 的距離是整棵樹中最長者之一（即樹中最長路徑之一）。
而樹直徑有一個特性——從任意節點出發走盡可能地遠（本題的「距離」即為價格和，以下將用「距離」替換大部分的「價格和」之詞），最後停下的位置必定是 L 或 R 之一（更嚴格地來說是，構成直徑端點的某一點。如定義所述，最長者可能不只一個）。
所以其實我們本題就是只要想辦法找到 L 和 R，然後找到 L 和 R 各自到每一個節點的「距離」。此時便可以知道每一個節點 i 作為根節點時所有路徑中價格和最大者——即 i 到 L 與 i 到 R 的兩個「距離」中最大者；而最小者很簡單，就是節點 i 本身。
L 或 R 到每一個節點各自的「距離」很好求。即從 L 和 R 各自進行一次深度優先搜尋（Depth First Search，DFS）即可。所以會得到兩個陣列來代表各自到每個節點的「距離」。
那 L 和 R 怎麼求？很簡單，直接利用樹直徑的特性即可。
也就是說我們從隨便一個點出發（範例程式碼中是以節點 0 作為起點），進行一個 DFS 後找到離起點最遠的節點。而這必定是 L 或 R 其中之一，這邊我們就定義第一個找到的節點是 L。
接著從 L 再進行一次 DFS，走到最遠處。此時必定會走到不是 L 的另一個直徑端點（除非這棵樹只有一個節點），將其定義為 R。這樣就找到兩個直徑的端點了。
所以接著從 R 進行最後一次 DFS，便可以開始計算所求的最大成本（L 的在求 R 時已經求過了，可以不用再掃一次）。
那為什麼這個特性是對的？雖然不正式，但以下是一點「直覺」式證明 + 反證法：
很明顯樹中必定存在最長路徑，即直徑。設其兩端點為 L 和 R。
假設此時有某一個點 i 走最長路徑走到的不是 L 和 R，且該路徑長度長於走到 L 和 R 的長度（不然如果小於等於的話，直接換成走到 L 和 R 即可）。假設該點為 X。則直徑實際上應為「L 到 X」、「R 到 X」、「L 到 i」或「R 到 i」之一才對，且長度更長。
而這違反了 L 到 R 是「最長路徑」之條件。因故，命題必成立。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
