[LeetCode]Fermat Point Of Graphs

这道题是Sums of Distances in Tree的带权版本，那么做法仍然是类似的。我们选择一个节点root当根，算出其他节点到root的距离，和每个以节点i为根的子树的大小size[i]。我们用dp[i]表示其他所有节点到i的距离和。那么我们有递推公式：

• dp[i] = dp[j] - size[i] * w(i, j) + (n - size[i]) * w(i, j), where j is i's parent
• 以i为根的子树的节点和i的距离比和j的距离减小了size[i] * w(i, j)
• 除了在i的子树中的节点和i的距离比和j的距离增加了(n - size[i]) * w(i, j)

其中n为所有节点的数量，w(i, j)表示连接i和j的边的权值。然我们dp是树形从上到下的dfs顺序。时间复杂度和空间复杂度均为O(n)，代码如下：