정올 전쟁 > 문제은행



문제은행

3192 : 정올 전쟁

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 14 회    시도횟수: 154 회   



어떤 중세 역사서에 따르면, 정올국은 n개의 영토로 이루어져 있었다. 정올국은 지형상 길을 많이 만들 수 없어서, (n-1)개의 길로 모든 영토를 다 연결해 놓았다. 어떤 두 영토를 고르더라도, 한 영토에서 다른 영토로 가는 경로는 유일했다고 전해진다.

 

정올국의 국왕인 호는 아들과 딸인 혁과 희에게 정올국의 영토들을 분배해 주기로 했었다. 분배해 준다는 것은 n개의 영토 중 몆 개를 혁의 영토로, 나머지를 희의 영토로 정해준다는 뜻이다. 사실, 혁과 희는 사이가 별로 좋지 않았다고 한다. 국왕 호가 몇 번이고 각각 다른 방식으로 영토를 분배해 보았지만, 그때마다 혁과 희가 전쟁을 일으켜서 영토 분배를 번복하던 일이 3번이나 있었다. 3차 정올 전쟁이 일어나서 또다시 국왕 호가 전쟁을 말리고 영토를 회수할 때 즈음, 국왕 호의 충실한 신하인 환이 다음과 같은 사실을 알아냈다. 형제들은 “약한 영토”를 발견하면 전쟁을 일으키는데, 그 약한 영토란 다음과 같이 정의된다: 다른 이웃한 영토 중 자신과 같은 소속의 영토가 하나도 없는 영토를 약한 영토라고 한다. 이런 약한 영토가 하나도 없게 영토를 분배한다면, 4차 정올 전쟁이 일어나지 않을 것이라는 것이 환의 발견이다.

 

국왕 호는 드디어 안도의 한숨을 내쉬며, 갑자기 환에게 다음과 같은 질문을 던졌다. 국왕인 자신이 영토 분배를 했을 경우 4차 정올 전쟁이 일어나지 않는 경우의 수가 얼마나 될까? 하고 말이다. 충신인 환이 당황하며, 사흘 안에 알아오겠다고 대답했으나 컴퓨터를 쓸 줄 모르는 환에게는 막막한 과제이다. 어서 그 질문에 대한 답을 하는 프로그램을 작성하여 타임머신을 타고 환에게 넘겨주도록 하자.

 

답이 매우 클 수 있으므로, 109 + 7로 나눈 나머지를 출력하라.

 

참고: 한 자식에게 모든 영토를 다 주는 경우도 가능하다.​ 




첫 줄에 정올국의 영토의 수인 정수 n이 입력된다.
그 다음 n-1개의 줄에 걸쳐 정수 u와 v가 입력된다. 이는 u와 v가 양방향 도로로 이어져 있다는 뜻이다.

2 <= n <= 105 , 1 <= u, v <= n

모든 도시는 직접 또는 간접적으로 연결되어 있음이 보장된다.
부분문제: 전체 점수의 40%의 입력 데이터는 2 <= n <= 20임을 보장한다.



혁와 희가 서로 전쟁을 하지 않게 정올국의 영토를 분배하는 모든 경우의 수를 출력하라.


5
1 2
1 3
3 4
3 5
4






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.