KOI 2차 2020 초3/중2- 등산 마니아 > 문제은행 : 정보올림피아드&알고리즘




4602 : 등산 마니아

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

동네 뒷 산에는 등산로가 있다. 등산로는 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​ 

 


부분문제

  1. (8점) 1번 오두막과 2번 오두막, 2번 오두막과 3번 오두막, ···, 과 같이 모든 i (1 ≤ i ≤ N − 1)에 대해 i번 오두막이 i + 1번 오두막과 오솔길로 이어짐.
  2. (11점) 1번 오두막과 다른 모든 오두막이 각각 오솔길로 이어짐.
  3. (19점) 1번 오두막에서 산을 내려가는 방향으로 갈 때, (1번 포함) 모든 오두막에서 내려가는 방향의 오솔길은 2개이거나 0개이다. 또, 내려가는 방향의 오솔길이 0개인 모든 오두막은 1번 오두막에서의 거리가 동일하다.
  4. (17점) N ≤ 100
  5. (14점) N ≤ 5,000
  6. (31점) 추가 제약 조건 없음.

입력형식

첫 번째 줄에 N이 주어진다. 다음 N −1개의 줄에 오두막 번호 두 개가 공백 하나를 사이에 두고 주어진다.

두 오두막이 오솔길로 이어져 있다는 뜻이다.​ 


출력형식

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


입력 예

3
1 2
2 3

출력 예

5

입력 예

8
6 2
7 5
3 4
5 6
1 5
4 1
8 6

출력 예

84


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP