시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 15 | 3 | 3 | 50.000% |
N개의 노드로 이루어진 트리가 주어진다. M을 단순 경로의 개수라고 했을 때, M = N(N-1)/2 이다.
단순 경로의 순서 없는 세 쌍은 총 M(M-1)(M-2)/6개가 있다. 좋은 경로의 세 쌍이란, 경로의 세 쌍 (A, B, C) 중에서 아래와 같은 조건 중 적어도 하나를 만족하는 세 쌍을 의미한다.
트리가 주어졌을 때, 좋은 경로의 세 쌍의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 N(4 ≤ N ≤ 300,000)이 주어진다.
둘째 줄부터 N-1개의 줄에 트리의 간선을 나타내는 두 정점이 주어진다. 정점 번호는 1번부터 시작한다.
좋은 경로의 세 쌍의 개수를 109+7로 나눈 나머지를 출력한다.
4 1 2 2 3 3 4
16
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
43484
예제 1의 경우 아래와 같은 세 쌍이 좋은 경로의 세 쌍이다.