등산 마니아 timer 2초 memory 128MB

동네 뒷 산에는 등산로가 있다. 등산로는 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점) 추가 제약 조건 없음.