推 ILoveErr: 打那麼長他媽誰看的完 12/22 18:00
推 sustainer123: 大師 12/22 18:02
推 pandix: 大師 12/22 18:03
推 NTHUlagka: 大師 12/22 23:29
834. Sum of Distances in Tree
給你一個n表示節點數量，和很多個邊表示的一個無向圖，求出一個陣列包含了每個點
到其他所有點的距離和。
Example：
https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist1.jpg
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.
思路：
1.最簡單求解的方法就是先建立圖形，接下來對每個點用dfs()求出對其他
點的距離並加總，時間複雜度是 O(n^2) ，測資的n很大所以提交時必然會TLE，我們必
須想辦法優化。
2.對於一個無向圖，我們可以把任意的點當成樹的 root 並讓其他node下垂，這樣看過去
圖形就會是一個m元樹，例如下圖分別以0和2作為root：
https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist1.jpg
0 2
/ \ / | \ \
1 2 或 0 3 4 5
/|\ /
3 4 5 1
3.我們可以先算出以其中一點（這邊用0）到其他所有點的和，以上面的圖片為例子，
定義 f(i) 為從所有點走到 i 點的距離之和，0 到所有點的距離為：
f(0) = 1 + 1 + 2 + 2 + 2 = 8
觀察看看如何以最小成本得到其他點的和，若我們要得到點2的和，他的距離為：
f(2) = 2 + 1 + 1 + 1 + 1 = 6。
4.觀察上面兩式的關係，我們已知點0的和（每一個點的目的地都是0，且0走到0不用動）
，原本每個節點走到 0 需要花費8的距離，當目的地改為 2 之後對於f(2) 來說節點1
需要多走一步，節點0也需要多走一步，而節點3、4、5少走一步，節點2是原點不必走所
以再少走一步，我們可以把 f(2) 表達如下：
f(2) = f(0)（0作為根的和） + 2（點0和1） - 3（點3、4、5） - 1（自己少走一步）
上式可再度簡化：
f(2) = f(0) + 2（節點總數減去「2為root的subtree」數量） - 4（2為root的subtree
節點數量）
= f(0) + N（節點總數） - 2*4 （2為root的subtree節點數量）= 6
我們只需要把一個點作為和的基礎（父節點），並計算要求解的新root的節點數量即可求
和，得出遞迴式：
f(i) = f(i的父節點) + 節點總數 - (2 * i為根的子樹節點數)
5.知道遞迴式之後，按照順序求出：
count[]：每個節點的子節點數量
ans[0]：到節點0的距離和，作為遞迴的初始值
ans[i]：到節點 i 的距離和
6.要求出上面三個遞迴所需的條件，可以用三次dfs求解，因為是無向圖所以要紀錄
走訪了哪些點避免進入死循環，因為這題算是一顆樹所以只需要記錄前個點即可。
JavaCode：
--------------------------------------
class Solution {
private int[] ans;
private int[] count;
private List<List<Integer>> graph;
private int N;
public int[] sumOfDistancesInTree(int N, int[][] edges) {
this.N = N;
graph = new ArrayList<>();
ans = new int[N];
count = new int[N];
Arrays.fill(count, 1);
for (int i = 0; i < N; ++i) {
graph.add(new ArrayList<>());
}
for (int[] edge: edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
dfs1(0, -1);
ans[0] = dfs2(0, -1);
dfs3(0, -1);
return ans;
}
private void dfs1(int node, int parent) {
for (int child : graph.get(node)) {
if (child != parent) {
dfs1(child, node);
count[node] += count[child];
}
}
}
private int dfs2(int node, int parent) {
int sum = 0;
for (int child : graph.get(node)) {
if (child != parent) {
sum += dfs2(child, node);
}
}
return sum + count[node] - 1;
}
private void dfs3(int node, int parent) {
for (int child : graph.get(node)) {
if (child != parent) {
ans[child] = ans[node] + N - 2*count[child];
dfs3(child, node);
}
}
}
}
--------------------------------------
你的下一句話是打那麼長他媽誰看的完
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.8.239 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671703192.A.B42.html