2012年3月 冬コンテスト Problem E: Multi Ending Story [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;
import static java.lang.Math.min;

public class Main {

  private final int N;

	private final int[] L;
	private final int[] R;

	private final long[] E;
	private final long[] U;
	private final long[] S;
	private final long[] D;

	public Main(int n, int[] l, int[] r) {
		N = n;
		L = l;
		R = r;

		E = new long[N + 1];
		U = new long[N + 1];
		S = new long[N + 1];
		D = new long[N + 1];
	}

	public void run() {
		for (int i = 1; i < N; i++)
			D[L[i]] = D[R[i]] = D[i] + 1;
		E[N] = 1;
		for (int i = N - 1; i > 0; i--) {
			E[i] = E[L[i]] + E[R[i]];
			U[i] = U[L[i]] + U[R[i]] + E[i];
			S[i] = min(S[L[i]] + S[R[i]] + D[i] + 2,
					min(S[L[i]] + 1 + U[R[i]] + E[R[i]], U[L[i]] + E[L[i]] + S[R[i]] + 1));
		}
		System.out.println(min(U[1], S[1]));
	}
	
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		final int N = sc.nextInt();
		final int[] L = new int[N];
		final int[] R = new int[N];
		for (int i = 1; i < N; i++) {
			L[i] = sc.nextInt();
			R[i] = sc.nextInt();
		}
		new Main(N, L, R).run();
	}

	public static void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}