13254번 - 연휴 스페셜 저지

N개의 도시와 N-1개의 도로로 이루어진 나라가 있다. 이 나라의 도시는 0번부터 N-1번까지 번호가 매겨져 있다. 모든 도로는 양방향이며, 두 도시를 연결한다.

단순 경로란 두 개 이상의 도시의 수열로, 한 도시가 수열에 두 번 이상 등장하지 않는다. 또한, 연속된 도시를 연결하는 도로가 있어야 한다. 이 나라의 임의의 두 도시 사이에는 단순 경로가 존재한다. 즉, 이 나라의 도로 네트워크는 트리 형태이다.

이 나라에는 M개의 가족이 살고 있다. 가족은 0번부터 M-1번까지 번호가 매겨져 있다. 모든 가족은 도시 하나에 거주하고 있으며, 여러 가족이 같은 도시에 거주할 수 있다.

연휴를 맞이해서 모든 가족은 이동할 임의의 도시를 하나 골랐다. 선택한 도시는 현재 거주하고 있는 도시와는 다르며, 각 도시를 선택할 확률은 모두 같다. 이동할 도시의 선택은 가족마다 모두 독립적이다. 연휴 기간 동안 모든 가족은 거주하고 있는 도시와 선택한 도시 사이의 단순 경로를 이용해서 이동한다.

각각의 가족이 어떤 도시를 선택했는지에 따라서, 모든 가족이 이용하는 도로가 생길 수도 있다. 이러한 도로의 개수를 L로 나타낸다. L의 기댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 N과 거주하고 있는 가족의 수 M이 주어진다. (2 ≤ N ≤ 51, 1 ≤ M ≤ 50)

둘째 줄부터 N-1개의 줄에는 도로가 연결하는 도시의 번호가 주어진다. 입력으로 주어지는 도로는 항상 트리를 이룬다.

마지막 줄에는 각각의 가족이 거주하고 있는 도시의 번호가 주어진다.

첫째 줄에 L의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10^-6까지 허용한다.

예제 1의 경우에 이 나라에 거주하는 가족은 하나밖에 없고, 거주하는 도시는 0번이다.

50%의 확률로 1번 도시를 고를 것이다. 이 경우에는 0-1만 모든 가족이 사용하는 도로이다. L = 1

50%의 확률로 2번 도시를 고른다. 이 경우에는 0-1과 1-2가 모든 가족이 사용하는 도로이다. L = 2

기댓값은 0.5*1 + 0.5*2 = 1.5이다.

예제 2의 경우에 25%의 확률로 두 가족이 2번 도시를 고른다. 이 경우는 0-1과 1-2가 모든 가족이 사용하는 도로이며, L = 2이다. 다른 경우는 0-1만 모든 가족이 사용하는 도로이다. 따라서, 정답은 0.25*2 + 0.75*1 = 1.25 이다.