서브 트리의 크기 합
시간 제한2초메모리 제한512 MB
트리의 모든 연결 부분그래프를 세고, 각 부분그래프의 정점 수 합을 1e9+7로 나눈 나머지를 구한다.
문제
양방향 트리 가 주어진다. 트리의 정점에는 번부터 번까지 번호가 붙어 있다.
의 서브 트리는 정점을 하나 이상 포함하는 의 연결된 부분 그래프를 뜻한다. 서브 트리의 크기는 그 안에 들어 있는 정점의 개수이다.
의 모든 서브 트리의 크기를 더한 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 이 주어진다. ()
다음 개의 줄에 트리의 간선이 한 줄에 하나씩 주어진다. 각 줄에는 간선으로 이어진 두 정점의 번호 와 가 주어진다. (, )
주어지는 간선은 항상 트리를 이룬다.
출력
첫째 줄에 모든 서브 트리의 크기의 합을 1,000,000,007로 나눈 나머지를 출력한다.