동네 뒷 산에는 등산로가 있다. 등산로는 \(N\)개의 작은 오두막들이 \(N −1\)개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 \(1\)이다. 어떤 오두막에서도 다른 모든 오두막으로 하나 이상의 오솔길을 따라 이동하는 것이 가능하다. 오두막들은 \(1\)번부터 \(N\)번까지 번호가 붙어 있으며, \(1\)번 오두막이 산 정상에 있다. \(1\)번 오두막에서 다른 오두막으로 가는 가장 짧은 길을 따라 가면서 거치는 모든 오솔길들은 항상 산을 내려가는 방향이다.

철수는 등산 마니아이다. 철수가 한 오두막에서 다른 오두막으로 갈 때는 항상 산 정상을 거치는 가장 짧은 길을 따라 간다. 이렇게 간 길의 다양성은 길에 포함된 오솔길의 개수로 정의된다. 두 번 이상 지나간 오솔길은 한 번만 센다는 것에 주의하라.

아래 그림은 가능한 하나의 상황을 보여 준다. 산 정상에 \(1\)번 오두막이 있고 3번 오두막과 \(4\)번 오두막이 오솔길로 이어져 있다.

아래 그림은 \(2\)번 오두막에서 \(7\)번 오두막으로 가는 가장 짧은 길을 보여준다.

아래 그림은 \(2\)번 오두막에서 \(7\)번 오두막으로, 정상을 거쳐서 가는 가장 짧은 길을 보여 준다.

등산로의 구성을 입력으로 받아 모든 가능한 \(i\), \(j\)의 쌍에 대해서(\(1 ≤ i\) < \(j ≤ N\)), 철수가 \(i\)번 오두막에서 \(j\)번 오두막으로 가는 길의 다양성의 총 합을 계산하는 프로그램을 작성하라.

• \(2 ≤ N ≤ 300,000 \)

첫 번째 줄에 \(N\)이 주어진다. 다음 \(N −1\)개의 줄에 오두막 번호 두 개가 공백 하나를 사이에 두고 주어진다. 두 오두막이 오솔길로 이어져 있다는 뜻이다.

첫 번째 줄에 문제의 정답을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2020 > 2차 대회 > 초등부 3번 / 중등부 2번