2577 醫院設定

時間限制: 1 s

空間限制: 32000 KB

題目等級 : 黃金 Gold

題目描述 Description

設有一棵二叉樹,如下圖

其中,圈中數字表示結點居民的人口.圈邊上數字表示結點編号,.現在要求在某個結點上建立一個醫院,使所有居民所走的路程之和為最小,同時約定,相鄰結點之間 的距離為1.如上圖中,若醫院建在:

1處：則距離之和=4+12+2*20+2*40=136

3處：則距離之和=4*2+13+20+40=81

…….

輸入描述 Input Description

第一行一個整數n，表示樹的結點數。（n<=100）

接下來的n行每行描述了一個結點的狀況，包含三個整數，整數之間用空格（一個或多個）分隔，其中：第一個數為居民人口數；第二個數為左連結，為0表示表連結；第三個數為右連結。

輸出描述 Output Description

一個整數，表示最小距離和。

樣例輸入 Sample Input

5

13 2 3

4 0 0

12 4 5

20 0 0

40 0 0

樣例輸出 Sample Output

81

資料範圍及提示 Data Size & Hint

無

Flyoed + 暴力