나무 위의 빗물
시간 제한1초메모리 제한512 MB
물이 루트에서 시작해 매초 각 정점이 자식 하나를 균등 확률로 골라 1단위씩 보낼 때, 물을 가진 정점들의 최종 기대 물량 평균을 구한다.
문제
\
트리란 사이클이 없는 연결 그래프를 말한다. 위 그림은 1번 정점을 루트로 하는 어떤 트리다.
사실 이 트리는 영훈이가 뒷마당에서 기르고 있는 나무이다. 어제 비가 왔기 때문에 트리의 1번 정점에는 W만큼의 물이 고여 있다. 1번 정점을 제외한 모든 정점에는 아직 물이 고여 있지 않다.
이제 매초마다 모든 정점은 아래 작업을 순서대로 반복한다.
- 물을 가지고 있고 자식 정점이 있다면, 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 같은 확률로 그중 하나를 고른다.
- 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아 둔다.
작업이 순서대로 진행되므로, 부모 정점에게 받은 물을 즉시 자식 정점에게 줄 수는 없다.
영훈이는 나무를 바라보면서 더 이상 물이 움직이지 않는 상태가 되었을 때 각 정점에 물이 얼마나 있게 될지 궁금해졌다. 더 이상 물이 움직이지 않을 때 i번 정점에 쌓인 물의 양의 기댓값을 Pi라 하자. 이때 Pi가 0보다 큰 정점들에 대해서 Pi들의 평균은 얼마가 될까?
입력
첫째 줄에 트리 노드의 수 N과 1번 노드에 고인 물의 양을 나타내는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 10^9)
다음 N-1줄에 걸쳐 트리에 존재하는 간선의 정보가 U V 형태로 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
이는 양 끝 정점이 각각 U와 V인 간선이 트리에 존재한다는 뜻이다.
입력으로 주어지는 트리는 항상 올바른 연결 트리이며, 루트는 항상 1번 정점이다.
출력
문제의 정답을 출력한다. 정답과의 차이가 10^-3 이하인 값은 모두 정답으로 인정된다.