Informatica Online Judge

  태풍의 아들 KDH [2168 / 0878]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net(33rd 김동현)]

Background

태풍의 아들 "KDH"(끄드흐라 읽는다)가 학교 근처에 있는 수원 종합운동장에서 콘서트를 열기로 했다. 그의 별명 "태풍의 아들"에서 알 수 있듯이, 그의 넘쳐나는 인기는 그가 가는 모든 곳마다 태풍을 불러일으킨다. 그리고, 이 태풍은 곧 송죽동을 휩쓸고 지나갈 것이다!

송죽동은 N개의 노드로 이루어진 하나의 연결된 트리 모양이다. 경기과학고등학교, KT wiz 야구장, 홈플러스, 불로만, 설빙 등 다양한 장소들이 N−1개의 길을 통해 모두 서로 연결되어 있다. 송죽동은 매우 번성한 곳이기 때문에 임의의 두 지점을 잇는 경로에 대해 그 경로상의 모든 도로에 1만큼의 교통량이 가산된다.

KDH가 몰고 온 태풍이 송죽동을 휩쓸고 지나가면, 송죽동의 각 지점은 p의 확률로 붕괴된다. 송죽동의 두 지점을 잇는 임의의 경로에 대해, 양 끝 점을 포함해서 경로 상에 있는 마을 중 하나라도 붕괴된다면 그 경로에 대해서는 교통량이 가산되지 않는다.

태풍 때문에 교통량이 줄어들면, 콘서트 수익도 자연히 줄어들 것이다. 태풍 이후 송죽동 교통량의 기댓값을 정확히 알 수 있다면 손해를 미리 대비할 수 있을 것이다. KDH를 도와주자!

Input

첫 번째 줄에는 송죽동의 지점 수 N (1≤N≤200000) 과 확률 p를 나타내는 두 정수 a와 b가 주어진다. (p=ab, a와 b는 각각 1 이상 109 이하)

다음 N−1줄에는 각 도로가 잇는 두 지점 ui, vi가 주어진다. (1≤ui,vi≤N)

입력은 연결된 트리 형태임이 보장된다.

Output

첫 번째 줄에 태풍이 분 이후 송죽동에 있는 모든 도로의 교통량 기댓값의 합을 나타내는 수를 출력한다.

즉, 구한 기댓값을 xy라 할 때, x×y−1 (mod 109+7)의 값을 출력한다. (단, y−1은 y의 109+7에 대한 모듈러 역원(modular inverse))

IO Example

입력
5 1 2
1 2
1 3
2 4
2 5

출력
375000005

* 설명 : 예제 출력은 19/8를 의미한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]