Submission #58793

---

Source Code Expand

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[] C, parent;
	static ArrayList<ArrayList<Integer>> child = new ArrayList<ArrayList<Integer>>();

	public static void main(String[] args) {
		N = sc.nextInt();
		C = new int[N];
		parent = new int[N];
		C[0] = sc.nextInt();
		parent[0] = -1;
		for (int i = 0; i < N; ++i) {
			child.add(new ArrayList<Integer>());
		}
		for (int i = 1; i < N; ++i) {
			parent[i] = sc.nextInt() - 1;
			C[i] = sc.nextInt();
			child.get(parent[i]).add(i);
		}
		int shift = 500;
		long[][] dp = new long[N][shift * 2 + 1];
		for (long[] a : dp) {
			Arrays.fill(a, 1L << 50);
		}
		for (int i = N - 1; i >= 0; --i) {
			for (int j = child.get(i).isEmpty() ? 0 : 1; j < dp[0].length; ++j) {
				int to = j - shift;
				long c = Math.abs(C[i] - to);
				for (int n : child.get(i)) {
					c += dp[n][j - 1];
				}
				if (j == 0) {
					dp[i][j] = c;
				} else {
					dp[i][j] = Math.min(c, dp[i][j - 1]);
				}
			}
		}
		long ans = Long.MAX_VALUE;
		for (int i = 0; i < dp[0].length; ++i) {
			ans = Math.min(ans, dp[0][i]);
		}
		System.out.println(ans);

	}
}

Submission Info

Judge Result