시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 0 0 0.000%

문제

N개의 노드로 이루어진 트리가 주어진다. M을 단순 경로의 개수라고 했을 때, M = N(N-1)/2 이다.

단순 경로의 순서 없는 세 쌍은 총 M(M-1)(M-2)/6개가 있다. 좋은 경로의 세 쌍이란, 경로의 세 쌍 (A, B, C) 중에서 아래와 같은 조건 중 적어도 하나를 만족하는 세 쌍을 의미한다.

  • 세 경로 A, B, C가 모두 서로 다른 노드로 이루어져 있다.
  • 세 쌍이 모두 교차한다. 즉, 경로 A, B가 적어도 한 정점을 공유하고, A, C도 적어도 한 정점을, B, C도 적어도 한 정점을 공유한다.

트리가 주어졌을 때, 좋은 경로의 세 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(4 ≤ N ≤ 300,000)이 주어진다.

둘째 줄부터 N-1개의 줄에 트리의 간선을 나타내는 두 정점이 주어진다. 정점 번호는 1번부터 시작한다.

출력

좋은 경로의 세 쌍의 개수를 109+7로 나눈 나머지를 출력한다.

예제 입력

4
1 2
2 3
3 4

예제 출력

16

예제 입력 2

13
1 2
1 3
1 4
2 5
2 6
3 7
4 8
7 9
9 10
10 11
11 12
12 13

예제 출력 2

43484

힌트

예제 1의 경우 아래와 같은 세 쌍이 좋은 경로의 세 쌍이다.

  • (1, 2), (1, 3), (1, 4)
  • (1, 2), (1, 3), (2, 3)
  • (1, 2), (1, 3), (2, 4)
  • (1, 2), (1, 4), (2, 3)
  • (1, 2), (1, 4), (2, 4)
  • (1, 2), (2, 3), (2, 4)
  • (1, 3), (1, 4), (2, 3)
  • (1, 3), (1, 4), (2, 4)
  • (1, 3), (1, 4), (3, 4)
  • (1, 3), (2, 3), (2, 4)
  • (1, 3), (2, 3), (3, 4)
  • (1, 3), (2, 4), (3, 4)
  • (1, 4), (2, 3), (2, 4)
  • (1, 4), (2, 3), (3, 4)
  • (1, 4), (2, 4), (3, 4)
  • (2, 3), (2, 4), (3, 4)

출처