九章演算法 | Google 面試題：Fermat Point of Graphs
撰文 | JZ
專欄 | 九章演算法
題目描述
有一個無向無環連通圖，每條邊透過兩個頂點x［i］，y［i］來描述，每條邊的長度透過d［i］來描述。求這樣的一個點p，使得其他點到p的距離和最小，如果有多個這樣的點p，返回編號最小的。
思路點撥
dp［i］ 代表以 i 為根的子樹中的結點到 i 結點的距離和，dp［i］ = sum（dp［j］ + np［j］ * d（i， j）），np［i］ 代表以 i 為根的子樹的所有結點的個數，np［i］ = sum（np［j］） + 1。
考點分析
該題算是比較難的一道題了，無向無環的連通圖，我們可以理解為一棵多叉樹，對於一棵多叉樹要求費馬點，顯然需要樹形dp，不過這裡我們需要dfs兩次，第一次先求出每個字數的節點數np［i］和子樹中的結點到 i 結點的距離和dp［i］，那麼在第二個dfs中就能求出費馬點的位置，具體的狀態轉移可以參考一下答案。
九章參考程式
https：//www。
jiuzhang。com/solution/f
ermat-point-of-graphs/
/**
* 本參考程式來自九章演算法，由 @華助教 提供。版權所有，轉發請註明出處。
* - 九章演算法致力於幫助更多中國人找到好的工作，教師團隊均來自矽谷和國內的一線大公司在職工程師。
* - 現有的面試培訓課程包括：九章演算法班，系統設計班，演算法強化班，Java入門與基礎演算法班，Android 專案實戰班，
* - Big Data 專案實戰班，演算法面試高頻題班， 動態規劃專題班
* - 更多詳情請見官方網站：http：//www。jiuzhang。com/？source=code
*/
public class Solution {
/**
* @param x： The end points set of edges
* @param y： The end points set of edges
* @param d： The length of edges
* @return： Return the index of the fermat point
*/
class Pair {
public int first；
public int second；
public Pair（int first， int second） {
this。first = first；
this。second = second；
}
}
long ans；
int idx；
void dfs1（int x， int f， List
np［x］ = 1；
dp［x］ = 0；
for （int i = 0； i < g。get（x）。size（）； i++） {
int y = g。get（x）。get（i）。first；
if （y == f） {
continue；
}
dfs1（y， x， g， np， dp）；
np［x］ += np［y］；
dp［x］ += dp［y］ + （long）g。get（x）。get（i）。second * np［y］；
}
}
void dfs2（int x， int f， long sum， List
for （int i = 0； i < g。get（x）。size（）； i++） {
int y = g。get（x）。get（i）。first；
if （y == f） {
continue；
}
long nextSum = dp［y］ + （sum - dp［y］ - （long）np［y］ * g。get（x）。get（i）。second） + （long）（n - np［y］） * g。get（x）。get（i）。second；
if （nextSum < ans || （nextSum == ans && x < idx）） {
ans = nextSum；
idx = y；
}
dfs2（y， x， nextSum， g， np， dp， n）；
}
}
public int getFermatPoint（int［］ x， int［］ y， int［］ d） {
// Write your code here
int n = x。length + 1；
List
for（int i = 0； i <= n； i++） {
g。add（new ArrayList
}
for （int i = 0； i < x。length； i++） {
g。get（x［i］）。add（new Pair（y［i］， d［i］））；
g。get（y［i］）。add（new Pair（x［i］， d［i］））；
}
int ［］ np = new int［n + 1］；
long ［］ dp = new long［n + 1］；
dfs1（1， 0， g， np， dp）；
ans = dp［1］；
idx = 1；
dfs2（1， 0， dp［1］， g， np， dp， n）；
return idx；
}
}