아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

서브 트리의 크기 합

시간 제한2초메모리 제한512 MB

요약
트리의 모든 연결 부분그래프를 세고, 각 부분그래프의 정점 수 합을 1e9+7로 나눈 나머지를 구한다.
난이도

보통10점 중 6점

유형
트리, 동적 계획법, 조합론, DFS
정답자
아직 제출이 없습니다

문제

양방향 트리 TT가 주어진다. 트리의 정점에는 00번부터 N−1N-1번까지 번호가 붙어 있다.

TT의 서브 트리는 정점을 하나 이상 포함하는 TT의 연결된 부분 그래프를 뜻한다. 서브 트리의 크기는 그 안에 들어 있는 정점의 개수이다.

TT의 모든 서브 트리의 크기를 더한 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 NN이 주어진다. (1≤N≤1051 \le N \le 10^5)

다음 N−1N-1개의 줄에 트리의 간선이 한 줄에 하나씩 주어진다. 각 줄에는 간선으로 이어진 두 정점의 번호 uu와 vv가 주어진다. (0≤u,v≤N−10 \le u, v \le N-1, u≠vu \ne v)

주어지는 간선은 항상 트리를 이룬다.

출력

첫째 줄에 모든 서브 트리의 크기의 합을 1,000,000,007로 나눈 나머지를 출력한다.

예제4

  1. 예제 1

    입력
    3
    0 1
    0 2
    
    예상 출력
    10
    
  2. 예제 2

    입력
    5
    0 1
    1 2
    1 3
    1 4
    
    예상 출력
    52
    
  3. 예제 3

    입력
    1
    
    예상 출력
    1
    
  4. 예제 4

    입력
    2
    0 1
    
    예상 출력
    4