20188 등산 마니아

import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.HashMap;
public class Test {
	static HashMap<Integer,ArrayList<Integer>> graph;
	static long[] dp = new long[300001];
	static long answer=0;
	static long N;
	public static void main(String[] args) throws IOException { 
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		graph = new HashMap<>();
		for(int i=1; i<=N; i++) graph.put(i,new ArrayList<>());
		
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		makeRoute(1); //root(정상): 1
		bw.write(answer-numberOfCase2(N)+"\n");//루트노드가 중복되서 들어가기 때문에 전체 경우의 수 빼줌
		bw.flush();
		bw.close();
	}
	static long makeRoute(int i) {
		dp[i]=1;
		for(int node : graph.get(i)) {
			if(dp[node]==0) dp[i] += makeRoute(node);
		}
		
		//전체에서 노드 2개 선택 경우의 수 - 부모 노드 포함한 서브트리에서 2개 선택 경우의 수
		answer += numberOfCase2(N)-numberOfCase2(N-dp[i]);
		
		return dp[i];
	}
	static long numberOfCase2(long n) { //2개 선택하는 경우의 수 -> nC2
		return n*(n-1)/2;
	}
}

 

보고 풀어도 어렵네 ..😶‍🌫️

이게 초등부 문제라구요..? ..