AOJ 1196 : 橋の撤去
ICPC諸島には島の数 n に対して n-1 個の橋があり，どの島から島へも， 橋を何回か渡れば到達することができるようになっている．
つまり木になっている。
それが分かればあとはやるだけとなる。
すべての頂点（島）を根と見なして探索し、
・移動コストが一番大きな遷移（根まで戻りたくないので）、
・端っこ（橋を渡る必要がないので）
を考える。
すべての辺（橋）のコスト（長さ）を考えうる最大回数3でかけて足し、
「大きな遷移」を引き、「端っこ」につながる辺のコスト x2で引けばよい。
例えばSample Inputの2番目のケースを島1を根して考えると、
最大の遷移（端っこは含めないことに注意）30と端っこの辺のコスト x2 = 12
を全体の合計 x3 = 196から引くと、
196 - 30 - 12 = 156
となる。なおこれは最小ではなく、島5か8を根にして考えたものが最小となる。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2369513#1
