Codeforces #57 (div2) D "Eternal Victory"

問題：http://codeforces.com/contest/61/problem/D

参加形式：本番

都市の数および都市をつなぐ道と距離のリストが与えられる．それぞれの都市に番号が1から振られていて，都市1からスタートしてすべての都市を回る道順を考えたとき，最短となるように進んで通った距離を求める．

与えられたグラフは都市1をルートとした木構造なので，すべての道を一回は通る必要がある．しかし，都市1に戻ってくる必要がないため，最後に訪れる都市から都市1への往路を省略できる．なので，すべての道の往復距離の合計と最も遠い場所への距離の差を取った．下記のコードはすべての道の合計を求めつつ都市1から最も遠い都市への距離を求めながらDFSしている．

コード

import java.util.*;

public class D {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		list = new ArrayList<List<int[]>>();
		for (int i = 0; i < n + 1; ++i) {
			list.add(new ArrayList<int[]>());
		}
		for (int i = 0; i < n - 1; ++i) {
			int u = s.nextInt(), v = s.nextInt(), w = s.nextInt();
			list.get(u).add(new int[] { v, w });
			list.get(v).add(new int[] { u, w });
		}
		b = new boolean[n + 1];
		b[1] = true;
		System.out.println(f(1, 0) - len);
	}

	static List<List<int[]>> list;
	static boolean[] b;
	static long len = 0;

	static long f(int i, long d) {
		long c = 0;
		len = Math.max(len, d);
		for (int[] is : list.get(i)) {
			if (!b[is[0]]) {
				b[is[0]] = true;
				c += 2 * is[1] + f(is[0], d + is[1]);
			}
		}
		return c;
	}
}