題目 3087:
信息學(xué)奧賽一本通T1338-醫(yī)院設(shè)置
時間限制: 2s
內(nèi)存限制: 192MB 提交: 33 解決: 15
題目描述
設(shè)有一棵二叉樹（如下圖），其中圈中的數(shù)字表示結(jié)點中居民的人口，圈邊上數(shù)字表示結(jié)點編號?，F(xiàn)在要求在某個結(jié)點上建立一個醫(yī)院，使所有居民所走的路程之和為最小，同時約定，相鄰結(jié)點之間的距離為1。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2×20+2×40=136；若醫(yī)院建在3處，則距離和=4×2+13+20+40=81……
輸入格式
第一行一個整數(shù)nn，表示樹的結(jié)點數(shù)（n≤100）。接下來的nn行每行描述了一個結(jié)點的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈接，為0表示無鏈接；第三個數(shù)為右鏈接，為0表示無鏈接。
輸出格式
一個整數(shù)，表示最小距離和。
樣例輸入
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0
樣例輸出
81