樹中的邊緣切割

Question

樹可以通過去除其中的一條邊而被分成兩棵不同的樹。給定一個帶有N節點的樹，該節點由[0, N-1]範圍內的整數唯一標識，我需要編寫一個函數來查找需要從樹中移除的邊，從而使得結果中所有節點ID的總和之差樹木被最小化。

該函數應打印它找到的與標準輸出（stdout）的最小差異。

該函數將接收下列參數：

parent這是整數的數組具有以下含義：parent[i] =節點i（更具體地其ID）

parent[i] = -1如果i具有的父沒有父（i是該樹的根）

數據約束

樹中的節點的最大數目爲50000個

效率約束

功能預計在小於2秒

打印結果實施例

Input parent: [1, 4, 4, 2, -1, 2, 2] 

aka :   4 
      /\ 
      1 2 
      // | \ 
      0 3 5 6 

Output: 9 

說明：我們刪除了節點2和節點6之間的邊。

Answer 1

1. 對於每個節點，計算其子節點的總和，然後將此值添加到自身，並將其存儲在節點中。我們稱這個值爲S_n，其中n是一個節點。 （可通過遞歸&後序遍歷很容易做到）

2. 找哪家S_n有向S_root/2差最小的節點n。 n和它的父代之間的邊是我們想要的邊。 （這在最壞的情況下需要線性時間。）