240717 등산 마니아

static int n;
static long result = 0;
static int[] dp;
static List<Integer>[] adjList;

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());

	n = Integer.parseInt(st.nextToken());

	initialize();

	for (int i = 1; i < n; i++) {
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		adjList[a].add(b);
		adjList[b].add(a);
	}

	calculateDP(1);
	System.out.println(result);
}

private static int calculateDP(int currentNode) {
	dp[currentNode] = 1;
	for (int neighbor : adjList[currentNode]) {
		if (dp[neighbor] == 0) {
			dp[currentNode] += calculateDP(neighbor);
		}
	}
	if (currentNode != 1) {
		result += combination(n) - combination(n - dp[currentNode]);
	}
	return dp[currentNode];
}

private static long combination(int n) {
	return (long) n * (long) (n - 1) / 2;
}

@SuppressWarnings("unchecked")
private static void initialize() {
	adjList = new ArrayList[n + 1];
	dp = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		adjList[i] = new ArrayList<>();
	}
}

출처:https://www.acmicpc.net/problem/20188