2012年4月 春コンテスト Problem J: Tree Allocation (貪欲にひと捻り加えてみました) [Licence: NYSL Version 0.9982]

Main.java

import java.util.*;
import java.io.*;

public class Main implements Runnable {
  private final int N, B;
	private final int[] next;

	public Main(final int n, final int b, final int[] nx) {
		N = n;
		B = b;
		next = nx;
	}

	@Override
	public void run() {
		// final int[][] depth = new int[N][2];
		// final int[][] size = new int[N][2];
		final int[][] max = new int[N][3];
		final int[][] siz = new int[N][3];
		final int[] ans = new int[N];
		final int[] retMax = new int[N];
		final int[] retSiz = new int[N];
		final int[] argMax = new int[N];
		final int[] argSiz = new int[N];

		// bottom up phase (dfs)
		{
			for (int k = N - 1; k >= 0; k--) {
				max[k][0] = 1;
				for (int i = next[k]; i < next.length; i = next[i]) {
					final int p = i - N + 1;
					for (int j = 0; j < 2; j++)
						if (retMax[p] > max[k][j]) {
							max[k][j + 1] = max[k][j];
							siz[k][j + 1] = siz[k][j];
							max[k][j] = retMax[p];
							siz[k][j] = retSiz[p];
							break;
						} else if (retMax[p] == max[k][j]) {
							siz[k][j] += retSiz[p];
							break;
						}
				}
				if (siz[k][0] < B) {
					retMax[k] = max[k][0];
					retSiz[k] = siz[k][0] + 1;
				} else {
					retMax[k] = max[k][0] + 1;
					retSiz[k] = 1;
				}
			}
		}
		// top down phase (bfs)
		{
			for (int k = 0; k < N; k++) {
				{
					final int d = Math.max(max[k][0], argMax[k]);
					final int s = (d == max[k][0] ? siz[k][0] : 0) + (d == argMax[k] ? argSiz[k] : 0);
					ans[k] = s < B ? d : d + 1;
				}

				for (int i = next[k]; i < next.length; i = next[i]) {
					final int p = i - N + 1;
					int d = 1;
					int s = 0;
					for (int j = 0; j < 2; j++)
						if (retMax[p] != max[k][j]) {
							d = Math.max(max[k][j], d);
							s = siz[k][j];
							break;
						} else if (siz[k][j] > retSiz[p]) {
							d = Math.max(max[k][j], d);
							s = siz[k][j] - retSiz[p];
							break;
						}
					final int dd = Math.max(d, argMax[k]);
					final int ss = (dd == d ? s : 0) + (dd == argMax[k] ? argSiz[k] : 0);
					if (ss < B) {
						argMax[p] = dd;
						argSiz[p] = ss + 1;
					} else {
						argMax[p] = dd + 1;
						argSiz[p] = 1;
					}
				}
			}
		}

		// output
		for (final int i : ans)
			System.out.println(i);
//		debug(max, siz);
//		debug(retMax, retSiz);
//		debug(argMax, argSiz);
	}

	public static void main(String... args) {
		final Scanner sc = new Scanner(System.in);
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		for(int T = 1; sc.hasNext(); T++) {
			System.gc();
			if(!solve(sc, T))
				break;
		}
		System.out.flush();
	}

	public static boolean solve(Scanner sc, int T) {
		final int N = Integer.parseInt(sc.next());
		final int B = Integer.parseInt(sc.next());
		if(N == 0 && B == 0)
			return false;
		final int[] next = new int[2 * N - 1];
		Arrays.fill(next, next.length);
		for (int i = 0; i < N - 1; i++) {
			final int j = Integer.parseInt(sc.next()) - 1;
			next[i + N] = next[j];
			next[j] = i + N;
		}
		System.out.println("Case " + T + ":");
		new Main(N, B, next).run();
		return true;
	}

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